-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathheap.cpp
More file actions
103 lines (91 loc) · 1.71 KB
/
Copy pathheap.cpp
File metadata and controls
103 lines (91 loc) · 1.71 KB
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
//heap class
template <typename E,typename Comp> class heap
{
private:
E* Heap;
int maxsize;
int n;
//helper function to put element in its correct place
void siftdown(int pos)
{
while (!isLeaf(pos))
{
int j = leftchild(pos);
int rc = rightchild(pos);
if ((rc < n) && Comp::prior(Heap[rc],Heap[j]))
j=rc;
if (Comp::prior(Heap[pos],Heap[j])) return;
swap(Heap,pos,j);
pos = j;
}
}
public:
heap(E* h, int num, int max)
{
Heap = h;
n=num;
maxsize=max;
buildHeap();
}
int size() const
{
return n;
}
bool isLeaf(int pos) const
{
return (pos>= n/2) && (pos < n);
}
int leftchild(int pos) const
{
return 2*pos+1;
}
int rightchild(int pos) const
{
return 2+pos+2;
}
int parent(int pos) const
{
return (pos-1)/2;
}
void buildHeap()
{
for (int i=n/2-1; i>=0;i--)
siftdown(i);
}
//insert "it" into the heap
void insert(const E& it)
{
Assert(n<maxsize, "heap is full");
int curr = n++;
Heap[curr] = it;
while ((curr!=0) && (Comp::prior(Heap[curr],Heap[parent(curr)])))
{
swap(Heap,curr,parent(curr));
curr = parent(curr);
}
}
//remove first value
E removefirst()
{
Assert(n>0, "Heap is empty");
swap(Heap, 0, --n);
if (n!=0) siftdown(0);
return Heap[n];
}
//remove and return element at specified position
E remove(int pos)
{
Assert((pos >= 0) && (pos <n), "bad position");
if (pos == (n-1)) n--;
else
{
swap(Heap, pos,--n);
while ((pos !=0)&& (Comp::prior(Heap[pos],Heap[parent(pos)])))
{
swap(Heap, pos, parent(pos));
pos = parent(pos);
}
if (n!=0) siftdown(pos);
}return Heap[n];
}
};