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