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
|
// Binary heaps using a straightforward implementation a la CLR
#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
void print() {
for (int i = 1; i <= size; i++) {
cout << data[i].key << " ";
}
cout << endl;
}
};
// 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()
{ int i, l, r, smallest;
Assert2(size > 0);
data[1] = data[size];
data[size].key = getSupremum();
size--;
i = 1;
for (;;) {
Debug3(print());
l = (i << 1);
r = (i << 1) + 1;
if ((l <= size) && data[l].key < data[i].key) {
smallest = l;
} else {
smallest = i;
}
if ((r <= size) && data[r].key < data[smallest].key) {
smallest = r;
}
if (smallest == i) break;
Element temp = data[i];
data[i] = data[smallest];
data[smallest] = temp;
i = smallest;
}
}
// 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);
size++;
int hole = size;
while (hole > 1 && data[hole >> 1].key > k) {
data[hole] = data[hole >> 1];
hole = hole >> 1;
}
data[hole].key = k;
data[hole].value = v;
}
#endif
|
