Heap
The (binary) heap data structure is an array object that we can view as a nearly complete binary tree.
An array A that represent a heap is an obejct with two attributes: $A.length$, $A.heap-size$
The root of the tree is $A[1]$, and given the index $i$ of a node, we can easily compute the indices of its parent, left child and right child.
The values in the nodes satisfy a heap property.
heap property
max-heap-property: A[parent(i)] >= A[i].
min-heap-property: A[parent(i)] <= A[i].
priority queue
often $heap$ is implemented as priority queue, because of space complexity of heap,
space complexity: $\Omicron(n)$
Operations
| Member Function |
Running Time |
| max_heapify() |
$\Omicron(lg(n))$ |
| build_max_heap() |
$\Omicron(n)$ |
| heapsort() |
$\Omicron(nlg(n))$ |
| max_heap_insert() |
$\Omicron(lg(n))$ |
| heap_increase_key() |
$\Omicron(lg(n))$ |
| heap_maximum() |
$\Omicron(lg(n))$ |
Applications
- HeapSort
- Priority queue: A priority queue is an abstract concept like "a list" or " map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with heap or a variety of other methods.
- Graph algorithms
- Selection algorithms
Implementation
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 | #include <iostream>
using namespace std;
template<typename T>
void _swap(T &a, T &b) {
T temp = a;
a = b;
b = temp;
}
template<typename T>
class heap {
int _size;
int _capacity;
T* _buf;
inline int parent(int i) {
return (i - 1) >> 1;
}
inline int left(int i) {
return (i << 1) + 1;
}
inline int right(int i) {
return (i << 1) + 2;
}
void max_heapify(int i) {
int largest;
int l = left(i);
int r = right(i);
if (l < _size && _buf[l] > _buf[i]) {
largest = l;
} else {
largest = i;
}
if (r < _size && _buf[r] > _buf[largest]) {
largest = r;
}
if (largest != i) {
_swap(_buf[largest], _buf[i]);
max_heapify(largest);
}
}
void reserve(int n) {
if (n <= _size) return;
T* temp = new T[n];
for (int i = 0; i < _size; i++) {
temp[i] = _buf[i];
}
_capacity = n;
delete[] _buf;
_buf = temp;
}
public:
heap(): _size(0), _capacity(0), _buf(0){}
heap(int n) {
_size = n;
_capacity = n;
_buf = new T[n];
for (int i = 0; i < n; i++) {
_buf[i] = rand()%400;
}
}
void build_max_heap() {
for (int i = parent(_size -1); i >= 0; i--)
max_heapify(i);
}
void heapsort() {
build_max_heap();
int original_size = _size;
for (int i = _size-1; i > 0; i--) {
swap(_buf[0], _buf[i]);
_size--;
max_heapify(0);
}
_size = original_size;
}
// priority queue;
T maximum() {
return _buf[0];
}
T extract_max() {
if (_size == 0) {
cout << "underflow";
return -1;
}
int max = _buf[0];
_buf[0] = _buf[--_size];
max_heapify(0);
return max;
}
void increase_key(int i, T key) {
if (key < _buf[i]) {
cout << "new key is smaller than current key" << endl;
return;
}
_buf[i] = key;
while(i > 0 && _buf[parent(i)] < _buf[i]) {
_swap(_buf[i], _buf[parent(i)]);
i = parent(i);
}
}
void insert(T key) {
if (_size == 0) {
reserve(1);
}
else if (_size == _capacity) {
reserve(_size << 1);
}
_buf[_size] = key-1;
increase_key(_size++, key);
}
void print() {
for (int i = 0; i < _size; i++) {
cout << _buf[i] << ' ';
}
cout << endl;
}
};
int main() {
heap<int> q(30); // make random heap;
cout << "================= random ===============" << endl;
q.print();
cout << "========== after build-max-heap=========" << endl;
q.build_max_heap();
q.print();
cout << "============ after heapsort ============" << endl;
q.heapsort();
q.print();
cout << "============ priority queue ===========" << endl;
heap<int> pq;
for (int i = 0; i < 1000; i++) {
pq.insert(rand()%100);
}
for (int i = 0; i < 1000; i++) {
cout << pq.extract_max() << ' ';
}
//pq.print();
return 0;
}
|