mpadge.tngl.sh
many-to-many multi-modal routing aggregator
1/* File bheap.c - Binary Heap
2 * ----------------------------------------------------------------------------
3 * Mark Padgham, adapted from code by Shane Saunders
4 */
5#include <cstdlib>
6#include "bheap.h"
7
8/* This implementation stores the binary heap in a 1 dimensional array. */
9
10
11/*--- BHeap (public methods) ------------------------------------------------*/
12
13/* --- Constructor ---
14 * Allocates and initialises a binary heap capable of holding n items.
15 */
16BHeap::BHeap(size_t n)
17{
18 // int i;
19
20 /* For the purpose of indexing the binary heap, we require n+1 elements in
21 * a[] since the indexing method does not use a[0].
22 */
23 a = new BHeapNode[n+1];
24 aPos = new size_t[n];
25 // for(i = 0; i <= n; i++) {
26 // a[i].item = 0;
27 // a[i].key = 0;
28 // }
29 // for(i = 0; i < n; i++) aPos[i] = 0;
30 itemCount = 0;
31 compCount = 0;
32}
33
34/* --- Destructor ---
35*/
36BHeap::~BHeap()
37{
38 delete [] a;
39 delete [] aPos;
40}
41
42/* --- min() ---
43 * Returns the item with the minimum key in the heap.
44 */
45size_t BHeap::min()
46{
47 /* the item at the top of the binary heap has the minimum key value */
48 return a[1].item;
49}
50
51// # nocov start - this function is not actually used here
52double BHeap::getmin()
53{
54 return a[1].key;
55}
56// # nocov end
57
58/* --- insert() ---
59 * Inserts an item $item$ with associated key value $key$ into the heap.
60 */
61void BHeap::insert(size_t item, double key)
62{
63 /* i - insertion point
64 * j - parent of i
65 * y - parent's entry in the heap
66 */
67 size_t i, j;
68 BHeapNode y;
69
70 /* $i$ initially indexes the new entry at the bottom of the heap */
71 i = ++itemCount;
72
73 /* stop if the insertion point reaches the top of the heap */
74 while(i >= 2) {
75 /* $j$ indexes the parent of $i$, and $y$ is the parent's entry */
76 j = i / 2;
77 y = a[j];
78
79 /* We have the correct insertion point when the items key is >= parent
80 * Otherwise we move the parent down and insertion point up.
81 */
82 compCount++;
83 if(key >= y.key) break;
84
85 a[i] = y;
86 aPos[y.item] = i;
87 i = j;
88 }
89
90 /* insert the new item at the insertion point found */
91 a[i].item = item;
92 a[i].key = key;
93 aPos[item] = i;
94}
95
96/* --- delete() ---
97 * Deletes item $item$ from the heap.
98 */
99void BHeap::deleteItem(size_t item)
100{
101 /* Decrease the number of entries in the heap and record the position of
102 * the item to be deleted.
103 */
104 const size_t n = --itemCount;
105 const size_t p = aPos[item];
106
107 /* Heap needs adjusting if the position of the deleted item was not at the
108 * end of the heap.
109 */
110 if(p <= n) {
111 /* We put the item at the end of the heap in the place of the deleted
112 * item and sift-up or sift-down to relocate it in the correct place in
113 * the heap.
114 */
115 compCount++;
116 if(a[p].key <= a[n+1].key) {
117 a[p] = a[n + 1];
118 aPos[a[p].item] = p;
119 siftUp(p, n);
120 }
121 else {
122 /* Use insert to sift-down, temporarily adjusting the size of the
123 * heap for the call to insert.
124 */
125 itemCount = p - 1;
126 insert(a[n+1].item, a[n+1].key);
127 itemCount = n;
128 }
129 }
130}
131
132/* --- decreaseKey() ---
133 * Decreases the value of $item$'s key to the value $newKey$.
134 */
135void BHeap::decreaseKey(size_t item, double newKey)
136{
137 const size_t n = itemCount;
138
139 itemCount = aPos[item] - 1;
140 insert(item, newKey);
141
142 itemCount = n;
143}
144
145/*--- BHeap (private methods) -----------------------------------------------*/
146
147/* --- siftUp() ---
148 * Considers the sub-tree rooted at index $p$ that ends at index $q$ and moves
149 * the root down, sifting up the minimum child until it is located in the
150 * correct part of the binary heap.
151 */
152void BHeap::siftUp(size_t p, size_t q)
153{
154 /* y - the heap entry of the root.
155 * j - the current insertion point for the root.
156 * k - the child of the insertion point.
157 * z - heap entry of the child of the insertion point.
158 */
159 size_t j, k;
160 BHeapNode y, z;
161
162 /* Get the value of the root and initialise the insertion point and child.
163 */
164 y = a[p];
165 j = p;
166 k = 2 * p;
167
168 /* sift-up only if there is a child of the insertion point. */
169 while(k <= q) {
170
171 /* Choose the minimum child unless there is only one. */
172 z = a[k];
173 if(k < q) {
174 compCount++;
175 if(z.key > a[k + 1].key) z = a[++k];
176 }
177
178 /* We stop if the insertion point for the root is in the correct place.
179 * Otherwise the child goes up and the root goes down. (i.e. swap)
180 */
181 if(y.key <= z.key) break;
182 a[j] = z;
183 aPos[z.item] = j;
184 j = k;
185 k = 2 * j;
186 }
187
188 /* Insert the root in the correct place in the heap. */
189 a[j] = y;
190 aPos[y.item] = j;
191}
192
193
194/*---------------------------------------------------------------------------*/