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
|
template<class ItemType>
struct HeapType
{
void ReheapDown(int root, int bottom);
void ReheapUp(int root, int bottom);
ItemType* elements;
int numElements;
};
template<class ItemType>
class PQType
{
public:
PQType(int);
~PQType();
void Enqueue(ItemType newItem);
void Dequeue(ItemType& item);
void Swap(ItemType&, ItemType&);
private:
int numItems;
HeapType<ItemType> items;
int maxItems;
};
template<class ItemType>
PQType<ItemType>::PQType(int max)
{
maxItems = max;
items.elements = new ItemType[max];
numItems = 0;
}
template<class ItemType>
PQType<ItemType>::~PQType()
{
delete[] items.elements;
}
template<class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem)
// Post: newItem is in the queue.
{
numItems++;
items.elements[numItems - 1] = newItem;
items.ReheapUp(0, numItems - 1);
}
template<class ItemType>
void PQType<ItemType>::Dequeue(ItemType& item)
{
item = items.elements[0];
items.elements[0] = items.elements[numItems - 1];
numItems--;
items.ReheapDown(0, numItems - 1);
}
template <class ItemType>
void PQType<ItemType>::Swap(ItemType& one, ItemType& two)
{
ItemType temp;
temp = one;
one = two;
two = temp;
}
template<class ItemType>
void HeapType<ItemType>::ReheapUp(int root, int bottom)
// Post: Heap property is restored.
{
int parent;
if (bottom > root)
{
parent = (bottom - 1) / 2;
if (elements[parent] < elements[bottom])
{
Swap(elements[parent], elements[bottom]);
ReheapUp(root, parent);
}
}
}
template<class ItemType>
void HeapType<ItemType>::ReheapDown(int root, int bottom)
// Post: Heap property is restored.
{
int maxChild;
int rightChild;
int leftChild;
leftChild = root * 2 + 1;
rightChild = root * 2 + 2;
if (leftChild <= bottom)
{
if (leftChild == bottom)
maxChild = leftChild;
else
{
if (elements[leftChild] <= elements[rightChild])
maxChild = rightChild;
else
maxChild = leftChild;
}
if (elements[root] < elements[maxChild])
{
Swap(elements[root], elements[maxChild]);
ReheapDown(maxChild, bottom);
}
}
}
|
