Min heap out of order
why is my min heap out of order?
when i input doubles into the heap, and then run extract min, i'm getting this output
41
153
288
292
491
778
1842
1869
2995
3035
3902
4664
4827
5436
5447
5705
6334
6868
7711
8723
8942
9040
9741
9894
9961
11478
11538
11942
12316
12382
12859
14604
14771
15141
15724
17035
17421
17673
18467
19264
18716
19169
19718
19912
21726
22190
22648
23281
23811
24464
25667
20037
26299
26500
25547
16827
26962
27644
19895
28145
27529
28253
28703
29358
30106
30333
31322
32391
32662
32757
|
as you can see some of them are not in order.
My guess: on line 126 of your code, you've used the wrong variable name.
HTH.
I'll put my code
graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void addVertex(int integer, int integer2, double a)
{
vertexList.push_back(new vertex(a));
if(y < integer2)
{
grid[x][y] = a;
y++;
}
else if(y == 7)
{
grid[x+1][0] = a;
y = 1;
x = x+1;
}
numofVertices++;
}
|
heap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
class Heap : public weightedGraph
{
public: Heap();
~Heap();
void insert(double *element);
double * deletemin();
void print();
int size(){return heap.size();}
private:
int left(int parent);
int right(int parent);
int parent(int child);
void heapifyup(int index);
void heapifydown(int index);
private:
vector<double*> heap;
};
Heap::Heap()
{}
Heap::~Heap()
{}
void Heap::insert(double *element)
{
heap.push_back(element);
heapifyup(heap.size()-1);
}
void Heap::heapifyup(int index)
{
while((index>0) && (parent(index) >=0) && (heap[parent(index)][1] > heap[index][1]))
{
double tmp[2];
tmp[0] = heap[parent(index)][0];
tmp[1] = heap[parent(index)][1];
heap[parent(index)][0] = heap[index][0];
heap[parent(index)][1] = heap[index][1];
heap[index][0] = tmp[0];
heap[index][1] = tmp[1];
index = parent(index);
}
}
void Heap::heapifydown(int index)
{
int child = left(index);
if ( ( child > 0 ) && ( right(index) > 0 ) &&
( heap[child][1] > heap[right(index)][1] ) )
{
child = right(index);
}
if ( child > 0 )
{
int tmp[2];
tmp[0] = heap[index][0];
tmp[1] = heap[index][1];
heap[index][0] = heap[child][0];
heap[index][1] = heap[child][1];
heap[child][0] = tmp[0];
heap[child][1] = tmp[1];
heapifydown(child);
}
}
double* Heap::deletemin()
{
double *min = heap.front();
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
return min;
}
void Heap::print()
{
vector<double *>::iterator pos = heap.begin();
cout << "Heap = ";
while ( pos != heap.end() ) {
cout << **pos << " "<<*(*pos+1) << " -" ;
++pos;
}
cout << endl;
}
int Heap::left(int parent)
{
int i = ( parent <<1) + 1;
return(i < heap.size() ) ? i : - 1;
}
int Heap::right(int parent)
{
int i = ( parent <<1) + 2;
return(i < heap.size() ) ? i : - 1;
}
int Heap::parent(int child)
{
if(child > 0)
{
int i = (child /2);
return i;
}
else return -1;
}
|
and then my cpp
1
2
3
4
5
6
|
while(i != 70)
{
dub = rand();
G.addVertex(a,b-2,dub);
i++;
}
|
help?
Topic archived. No new replies allowed.