/
heapoverall.cpp
103 lines (89 loc) · 2.03 KB
/
heapoverall.cpp
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
#include "heapoverall.h"
Heap::Heap()
{
}
Heap::~Heap()
{
}
void Heap::insert(float element)
{
heap.push_back(element);
heapifyup(heap.size() - 1);
}
float Heap::deletemin()
{
//int min = heap.front();
float min = heap.front();
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
return min;
}
void Heap::print()
{
// vector<int>::iterator pos = heap.begin();
vector<float>::iterator pos = heap.begin();
cout << "Heap = ";
while ( pos != heap.end() ) {
cout << *pos << " ";
++pos;
}
cout << endl;
}
void Heap::heapifyup(int index)
{
//cout << "index=" << index << endl;
//cout << "parent(index)=" << parent(index) << endl;
//cout << "heap[parent(index)]=" << heap[parent(index)] << endl;
//cout << "heap[index]=" << heap[index] << endl;
while ( ( index > 0 ) && ( parent(index) >= 0 ) &&
( heap[parent(index)] > heap[index] ) )
{
int tmp = heap[parent(index)];
heap[parent(index)] = heap[index];
heap[index] = tmp;
index = parent(index);
}
}
void Heap::heapifydown(int index)
{
//cout << "index=" << index << endl;
//cout << "left(index)=" << left(index) << endl;
//cout << "right(index)=" << right(index) << endl;
int child = left(index);
if ( ( child > 0 ) && ( right(index) > 0 ) &&
( heap[child] > heap[right(index)] ) )
{
child = right(index);
}
if ( child > 0 && heap[index]>= heap[child] )
{
float tmp = heap[index];
heap[index] = heap[child];
heap[child] = tmp;
heapifydown(child);
}
}
int Heap::left(int parent)
{
int i = ( parent << 1 ) + 1; // 2 * parent + 1
return ( i < heap.size() ) ? i : -1;
}
int Heap::right(int parent)
{
int i = ( parent << 1 ) + 2; // 2 * parent + 2
return ( i < heap.size() ) ? i : -1;
}
int Heap::parent(int child)
{
if (child != 0)
{
int i = (child - 1) >> 1;
return i;
}
return -1;
}
int Heap::size()
{
return heap.size();
}