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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
// 4ary heap data structure
#ifndef HEAP2
#define HEAP2
#include "util.h"
template <class Key, class Value>
struct KNElement {Key key; Value value;};
// fixed size binary heap
template <class Key, class Value>
class Heap2 {
// static const Key infimum = 4;
//static const Key supremum = numeric_limits<Key>.max();
typedef KNElement<Key, Value> Element;
Element *data;
int capacity;
int supremum;
int size; // index of last used element
public:
Heap2(Key sup, Key infimum, int cap):size(0),capacity(cap) {
data = new Element[cap + 2];
data[0].key = infimum; // sentinel
data[capacity + 1].key = sup;
supremum = sup;
reset();
}
~Heap2() { delete data; }
Key getSupremum() { return supremum; }
void reset();
int getSize() const { return size; }
Key getMinKey() const { return data[1].key; }
Value getMinValue() const { return data[1].value; }
void deleteMinBasic();
void deleteMin(Key *key, Value *value) {
*key = getMinKey();
*value = getMinValue();
deleteMinBasic();
}
void insert(Key k, Value v);
void sortTo(Element *to); // sort in increasing order and empty
//void sortInPlace(); // in decreasing order
};
// reset size to 0 and fill data array with sentinels
template <class Key, class Value>
inline void Heap2<Key, Value>::
reset() {
size = 0;
Key sup = getSupremum();
int cap = capacity;
for (int i = 1; i <= cap; i++) {
data[i].key = sup;
}
// if this becomes a bottle neck
// we might want to replace this by log KNN
// memcpy-s
}
template <class Key, class Value>
inline void Heap2<Key, Value>::
deleteMinBasic()
{
Assert2(size > 0);
// first move up elements on a min-path
int hole = 1;
int succ = 2;
int sz = size;
Element *dat = data;
while (succ < sz) {
Key key1 = dat[succ].key;
Key key2 = dat[succ + 1].key;
if (key1 > key2) {
succ++;
dat[hole].key = key2;
dat[hole].value = dat[succ].value;
} else {
dat[hole].key = key1;
dat[hole].value = dat[succ].value;
}
hole = succ;
succ <<= 1;
}
// bubble up rightmost element
Key bubble = dat[sz].key;
int pred = hole >> 1;
while (dat[pred].key > bubble) { // must terminate since min at root
dat[hole] = dat[pred];
hole = pred;
pred >>= 1;
}
// finally move data to hole
dat[hole].key = bubble;
dat[hole].value = dat[sz].value;
dat[size].key = getSupremum(); // mark as deleted
size = sz - 1;
}
// empty the heap and put the element to "to"
// sorted in increasing order
template <class Key, class Value>
inline void Heap2<Key, Value>::
sortTo(Element *to)
{
const int sz = size;
const Key sup = getSupremum();
Element * const beyond = to + sz;
Element * const root = data + 1;
while (to < beyond) {
// copy minimun
*to = *root;
to++;
// bubble up second smallest as in deleteMin
int hole = 1;
int succ = 2;
while (succ <= sz) {
Key key1 = data[succ ].key;
Key key2 = data[succ + 1].key;
if (key1 > key2) {
succ++;
data[hole].key = key2;
data[hole].value = data[succ].value;
} else {
data[hole].key = key1;
data[hole].value = data[succ].value;
}
hole = succ;
succ <<= 1;
}
// just mark hole as deleted
data[hole].key = sup;
}
size = 0;
}
template <class Key, class Value>
inline void Heap2<Key, Value>::
insert(Key k, Value v)
{
Assert2(size < capacity);
Debug4(cout << "insert(" << k << ", " << v << ")" << endl);
Element *dat = data;
size++;
int hole = size;
int pred = hole >> 1;
Key predKey = dat[pred].key;
while (predKey > k) { // must terminate due to sentinel at 0
dat[hole].key = predKey;
dat[hole].value = dat[pred].value;
hole = pred;
pred >>= 1;
predKey = dat[pred].key;
}
// finally move data to hole
dat[hole].key = k;
dat[hole].value = v;
}
#endif
|
