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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
// PriorityQueue.h
#include <vector>
using namespace std;
template <class T>
void print_vector(const vector<T>&);
template <class R>
void swap1 (R& x, R& y)
{
R temp = x;
x = y;
y = temp;
}
template <class T>
class PriorityQueue
{
public:
bool empty() {return heap.empty();}
int size() {return heap.size();}
T& top() {return heap[0];}
void push(T& newElement)
{
heap.push_back(newElement);
push_heap();
}
void pop() {pop_heap();}
void print_tree_aux(int pos, int level) const;
// define void print_tree()
void print_tree();
private:
void push_heap();
void pop_heap();
void adjust_heap();
vector<T> heap;
};
template <class T>
void PriorityQueue<T>::push_heap()
{ // push a value onto the priority queue
int position = heap.size() - 1;
int parent = (position - 1) / 2; // integer division
while (position > 0 && heap[position] > heap[parent])
{ // bubble up value as far as is necessary
swap1(heap[position], heap[parent]);
position = parent;
parent = (position - 1) / 2;
}
}
template <class T>
void PriorityQueue<T>::pop_heap()
{ // remove root and adjust heap
int lastpos = heap.size() - 1;
swap1(heap[0],heap[lastpos]); //swap root with last position
heap.pop_back(); // remove last position
adjust_heap(); // call adjust_heap
}
template <class T>
void PriorityQueue<T>::adjust_heap()
{ // restructures heap as necessary
int position = 0; // position of root
int heapSize = heap.size();
while (position < heap.size())
{
// position is within heap to adjust ..
// get pos of left chld;
int childpos = position * 2 + 1; // index of left child
if (childpos < heapSize)
{
// there is a left child within heap to adjust;
// is this the larger child? if there exists a right
// child within the heap to adjust, and this right
// child is larger, set childpos to the index of the
// larger child; (otherwise, just keep index of left
// child;
if ((childpos + 1 < heapSize) &&
heap[childpos + 1] > heap[childpos])
childpos++;
// if value at position is larger than the
// larger child, then the value is in its
// proper place; done;
if (heap[position] > heap[childpos])
return;
else
swap(heap[position],heap[childpos]); // swap value with larger child;
}
position = childpos;
}
}
template <class T>
void PriorityQueue<T>::print_tree_aux(int pos, int level) const
{ // prints tree using dots to indicate level of value in the tree
if (heap.empty())
{
cout << "empty" << endl;
return;
}
// print level many dots followed by value at index pos;
for (int i = 1; i <= level; i++)
cout << ".";
cout << heap[pos] << endl;;
if (2 * pos + 1 >= heap.size())
return; // value at pos is a leaf;
print_tree_aux(2 * pos+ 1, level + 1); // print left subtree;
if (2 * pos + 2 < heap.size())
print_tree_aux(2 * pos + 2, level + 1); // print right subtree;
}
template <class T>
void print_vector(const vector<T>& vec)
{ // print contents of a vector
cout << endl;
for (int i = 0; i < vec.size(); i++)
cout << vec[i] << " ";
cout << endl << endl;
}
template <class T>
void print_tree()
{
}
|
