I'm implementing a heapSort, using min-heap, and it sorts fine, below ~350 elements. Once the array has approximately 350 elements, it doesn't sort correctly. I'm not sure where the error lies, but I believe it might have to do with extractMin(), or something to do with recursion. I added the whole minHeap class to be thorough and to make sure the bug is not somewhere else.
Here is my code:
starting with the minHeap class:
#include <iostream>
using namespace std;
class minHeap
{
private:
double * items;
int numItems;
int capacity;
//suplimental functions
int parent(int i) { return (i - 1) / 2; }
int lchild(int i) { return 2 * i + 1; }
int rchild(int i) { return lchild(i) + 1; }
void bubbleUp(int i)
{
if (items[i] < items[parent(i)])
{
swap(items[i], items[parent(i)]);
bubbleUp(parent(i));
}
}
void bubbleDown(int i)
{
if(lchild(i) > (numItems-1))
{}
else
{
//boundary condition for only lchild left
if(rchild(i) > (numItems-1))
{
if(items[i] > items[lchild(i)])
{
swap(items[i],items[lchild(i)]);
bubbleDown(lchild(i));
}
}
//when everything is fine
else
{
if(items[lchild(i)] < items[rchild(i)])
{
if(items[i] > items[lchild(i)])
{
swap(items[i],items[lchild(i)]);
bubbleDown(lchild(i));
}
}
else if(items[lchild(i)] > items[rchild(i)])
{
if(items[i] > items[rchild(i)])
{
swap(items[i],items[rchild(i)]);
bubbleDown(rchild(i));
}
}
}
}
}
public:
minHeap()
{
capacity = 100;
numItems = 0;
items = new double[capacity];
}
minHeap(int c)
{
capacity = c;
numItems = 0;
items = new double[c];
}
void insert(int x)
{
items[numItems] = x;
numItems++;
bubbleUp(numItems -1);
}
here is extractMin(Still part of the minHeap class), which could be the culprit:
double extractMin()
{
double min = items[0];
swap(items[numItems - 1], items[0]);
numItems--;
bubbleDown(0);
return min;
}
};
the heapSort function (not associated with the minHeap class):
void heapSort(double *items, int start, int end)
{
minHeap list(end+1);
for(int i = start; i < end+1; i++)
list.insert(items[i]);
for(int i = start; i < end+1; i++)
items[i] = list.extractMin();
}
My main:
#include <iostream>
#include <string>
#include "minHeap.h"
#include "heapSort.h"
using namespace std;
int main()
{
double * numbers;
int max = 350;
numbers = new double[max];
//randomly fill array
for(int i=0; i<max; i++)
numbers[i] = rand();
heapSort(numbers,0,max-1);
cout << "sorted:" << endl;
for(int i=0; i<max; i++)
cout << numbers[i] << endl;
return 0;
}
The output I get:
5075
5097
5249
5447
5535
5537
5699
5829
5844
6038
6191
6224
6270
6359
6422
6483
6617
6618
6729
6868
7129
7376
7441
7448
7616
7711
7958
8281
8313
8723
8909
9040
9161
9374
9503
9512
9514
9741
9758
9789
9832
9894
10021
10285
10291
10322
10383
10466
10555
10585
10712
11008
11020
11173
11323
11337
11511
11538
11701
11840
12044
12052
12287
12292
12316
12423
12455
12529
12623
12859
12949
13030
13186
13290
13401
13458
13931
13966
13977
14309
14310
14343
14688
14771
14798
14893
14945
14989
15006
15141
15255
15281
15350
15457
15573
15574
15890
16105
16118
16139
16202
16279
16282
16413
16423
16512
16519
16541
16549
16687
16941
16944
17035
17189
17253
17410
17437
17451
17673
17807
17861
18007
18060
18190
18538
18588
18636
18651
18756
18762
18875
18935
19072
19156
19558
19589
19629
19668
19796
19815
18127
10808
19264
19866
12263
5786
9930
18114
19912
19954
19976
20024
20037
20053
20055
20142
20222
20328
20416
20450
20472
20485
20537
20580
20600
20649
20671
20798
20945
21003
21425
21538
21548
21659
21718
21724
21726
21881
22190
22355
22386
22483
22549
22646
22648
22704
22798
22813
22888
22929
23195
23196
23199
23622
23646
23655
23757
23805
23811
23844
23986
24021
24084
24179
24182
24221
24272
24350
24355
24370
24389
24393
24484
24488
24626
24648
24767
24946
25200
25547
6900
8942
4639
4734
25667
25721
25734
25996
26154
26292
26299
26308
26362
26418
26439
26777
26869
26924
27088
27157
27348
27350
27446
27506
27529
27595
27624
27644
27753
27756
27892
27938
27982
28009
28022
28253
28286
28321
28433
28476
4313
4313
28617
28692
28703
28745
29168
29314
29510
29657
29658
29869
30106
30145
30191
30303
30333
30523
30836
30932
31101
31107
31115
31185
31316
31322
31329
31426
31556
31673
31998
32209
32439
32591
32609
32662
32702
32757
14018
Press any key to continue . . .
This following line in your code: (in method bubbleDown)
else if(items[lchild(i)] > items[rchild(i)])
shall be:
else if(items[lchild(i)] >= items[rchild(i)])
or simply:
else
Or, your bubbleDown method may become incorrect when there are duplicated elements in the data.
UPDATED: Just FYI that in your sample data of 299 integers, there are two 4313