Binary trees
Difference
Some data structures to keep in my mind.
- BinaryHeap: Complete binary tree
- MaxHeap: Parent > Both Children
- IndexMaxHeap
- MinHeap: Parent < Both Children
- IndexMinHeap
- Priority queue (MaxHeap)
- BinarySearchTree
- Not always complete binary tree
- Value: leftChild < Parent < rightChild
- DenseGraph
- SparseGraph
Code snippets are taken from Play with Algorithm
Heap
The min-max heap property is: each node at an even level in the tree is less than all of its descendants, while each node at an odd level in the tree is greater than all of its descendants
1. MaxHeap
A-Max Heap is a Complete Binary Tree. A-Max heap is typically represented as an array.
if the root element index starts from Array[1]
1
2
3
| Arr[i/2] Returns the parent node.
Arr[2*i] Returns the left child node.
Arr[2*i+1] Returns the right child node.
|
if the root element index starts from Array[0]
1
2
3
| Arr[(i-1)/2] Returns the parent node.
Arr[2*i + 1] Returns the left child node.
Arr[2*i + 2] Returns the right child node.
|
How to construct MaxHeap:
- store values into an Array
- find the last node’s parent
- shiftDown (see code)
Example Code:
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
| #include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <cmath>
#include <cassert>
using namespace std;
template<typename Item>
class MaxHeap {
private:
Item *data;
int count;
int capacity;
/// helper func: construct max-heap, shift the last item up
void shiftUp(int k) {
// k: index of the data array
Item e = data[k];
// parent: k/2, child: k
// if k >=2 ( count > 2 ), then swap
while( k > 1 && data[k/2] < data[k] ) {
// swap( data[k/2], data[k] );
data[k] = data[k/2];
k /= 2;
}
data[k] = e;
}
/// helper func: shift the root item down
void shiftDown(int k) {
Item e = data[k];
while( 2*k <= count ) {
int j = 2*k;
// which child is larger. left: j, right: j+1
if( j+1 <= count && data[j+1] > data[j] ) j ++; // select right child
if( data[k] >= data[j] ) break;
// swap( data[k] , data[j] ); // swap parent and child
data[k] = data[j];
// shift down to child
k = j;
// data[j] 是 data[2*k]和data[2*k+1]中的最大值
}
data[k] = e;
}
public:
MaxHeap(int capacity){
data = new Item[capacity+1];
count = 0;
this->capacity = capacity;
}
MaxHeap(Item arr[], int n) {
data = new Item[n+1];
capacity = n;
// init a new array, store values data[1...]
for( int i = 0 ; i < n ; i ++ )
// note: heap index start position 1
data[i+1] = arr[i];
count = n;
// construct maxheap
for( int i = count/2 ; i >= 1 ; i -- )
// note: heap index start position 1
shiftDown(i);
}
~MaxHeap(){ delete[] data; }
int size(){ return count; }
bool isEmpty(){ return count == 0; }
void insert(Item item)
{
assert( count + 1 <= capacity );
// note: we init count == 0
data[count+1] = item; // append the new item to array.
shiftUp(count+1); // the last item
count ++;
}
/// heap sort
Item extractMax()
{
assert( count > 0 );
Item ret = data[1];
// put the max element to last node, then heapify again
swap( data[1] , data[count] );
count --;
shiftDown(1); // note: update maxheap, start from root node
return ret;
}
Item getMax()
{
assert( count > 0 );
return data[1];
}
};
// 测试最大堆
int main() {
MaxHeap<int> maxheap = MaxHeap<int>(100);
srand(time(NULL));
int n = 100; // 随机生成n个元素放入最大堆中
// heapify
for( int i = 0 ; i < n ; i ++ ){
maxheap.insert( rand()%100 );
}
int* arr = new int[n];
// heap sort
// 将maxheap中的数据逐渐使用extractMax取出来
// 取出来的顺序应该是按照从大到小的顺序取出来的
for( int i = 0 ; i < n ; i ++ ){
arr[i] = maxheap.extractMax();
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
|
2. IndexMaxHeap
Need 3 vector: data, indexes, reverse
Code
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
| #include <algorithm>
#include <cassert>
using namespace std;
template<typename Item>
class IndexMaxHeap {
private:
Item *data;
int *indexes;
int *reverse;
int count;
int capacity;
void shiftUp( int k ){
while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
swap( indexes[k/2] , indexes[k] );
reverse[indexes[k/2]] = k/2;
reverse[indexes[k]] = k;
k /= 2;
}
}
void shiftDown( int k ) {
while( 2*k <= count ) {
int j = 2*k;
if( j + 1 <= count && data[indexes[j+1]] > data[indexes[j]] )
j += 1;
if( data[indexes[k]] >= data[indexes[j]] )
break;
swap( indexes[k] , indexes[j] );
reverse[indexes[k]] = k;
reverse[indexes[j]] = j;
k = j;
}
}
public:
IndexMaxHeap(int capacity){
data = new Item[capacity+1];
indexes = new int[capacity+1];
reverse = new int[capacity+1];
for( int i = 0 ; i <= capacity ; i ++ )
reverse[i] = 0;
count = 0;
this->capacity = capacity;
}
~IndexMaxHeap(){
delete[] data;
delete[] indexes;
delete[] reverse;
}
int size() { return count; }
bool isEmpty() { return count == 0; }
// 传入的i对用户而言,是从0索引的
void insert(int i, Item item) {
assert( count + 1 <= capacity );
assert( i + 1 >= 1 && i + 1 <= capacity );
i += 1;
data[i] = item;
indexes[count+1] = i;
reverse[i] = count+1;
count++;
shiftUp(count);
}
Item extractMax() {
assert( count > 0 );
Item ret = data[indexes[1]];
swap( indexes[1] , indexes[count] );
reverse[indexes[count]] = 0;
reverse[indexes[1]] = 1;
count--;
shiftDown(1);
return ret;
}
int extractMaxIndex() {
assert( count > 0 );
int ret = indexes[1] - 1;
swap( indexes[1] , indexes[count] );
reverse[indexes[count]] = 0;
reverse[indexes[1]] = 1;
count--;
shiftDown(1);
return ret;
}
Item getMax(){
assert( count > 0 );
return data[indexes[1]];
}
int getMaxIndex(){
assert( count > 0 );
return indexes[1]-1;
}
bool contain( int i ){
assert( i + 1 >= 1 && i + 1 <= capacity );
return reverse[i+1] != 0;
}
Item getItem( int i ){
assert( contain(i) );
return data[i+1];
}
void change( int i , Item newItem ){
assert( contain(i) );
i += 1;
data[i] = newItem;
// 找到indexes[j] = i, j表示data[i]在堆中的位置
// 之后shiftUp(j), 再shiftDown(j)
// for( int j = 1 ; j <= count ; j ++ )
// if( indexes[j] == i ){
// shiftUp(j);
// shiftDown(j);
// return;
// }
int j = reverse[i];
shiftUp( j );
shiftDown( j );
}
};
|
BinarySearchTree
All property see the code.
- preorder
- inorder
- postorder
- BFS
- DFS
Example Code:
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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
| #include <iostream>
#include <queue>
#include <cassert>
using namespace std;
template <typename Key, typename Value>
class BST{
private:
struct Node{
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value) {
this->key = key;
this->value = value;
this->left = this->right = NULL;
}
Node(Node *node) {
this->key = node->key;
this->value = node->value;
this->left = node->left;
this->right = node->right;
}
};
Node *root;
int count;
public:
BST(){
root = NULL;
count = 0;
}
~BST(){
destroy( root );
}
int size() { return count; }
bool isEmpty() { return count == 0; }
void insert(Key key, Value value) {
root = insert(root, key, value);
}
bool contain(Key key) {
return contain(root, key);
}
Value* search(Key key){
return search( root , key );
}
// 前序遍历
void preOrder() { preOrder(root); }
// 中序遍历
void inOrder() { inOrder(root); }
// 后序遍历
void postOrder() { postOrder(root); }
// 层序遍历
void levelOrder() {
queue<Node*> q;
q.push(root);
while( !q.empty() ) {
Node *node = q.front();
q.pop();
cout<<node->key<<endl;
if( node->left )
q.push( node->left );
if( node->right )
q.push( node->right );
}
}
// 寻找最小的键值
Key minimum() {
assert( count != 0 );
Node* minNode = minimum( root );
return minNode->key;
}
// 寻找最大的键值
Key maximum() {
assert( count != 0 );
Node* maxNode = maximum(root);
return maxNode->key;
}
// 从二叉树中删除最小值所在节点
void removeMin() {
if( root )
root = removeMin( root );
}
// 从二叉树中删除最大值所在节点
void removeMax(){
if( root )
root = removeMax( root );
}
// 从二叉树中删除键值为key的节点
void remove(Key key) {
root = remove(root, key);
}
private:
// 向以node为根的二叉搜索树中,插入节点(key, value)
// 返回插入新节点后的二叉搜索树的根
Node* insert(Node *node, Key key, Value value) {
if( node == NULL ) {
count ++;
return new Node(key, value);
}
if( key == node->key )
node->value = value;
else if( key < node->key )
node->left = insert( node->left , key, value);
else // key > node->key
node->right = insert( node->right, key, value);
return node;
}
// 查看以node为根的二叉搜索树中是否包含键值为key的节点
bool contain(Node* node, Key key) {
if( node == NULL )
return false;
if( key == node->key )
return true;
else if( key < node->key )
return contain( node->left , key );
else // key > node->key
return contain( node->right , key );
}
// 在以node为根的二叉搜索树中查找key所对应的value
Value* search(Node* node, Key key) {
if( node == NULL )
return NULL;
if( key == node->key )
return &(node->value);
else if( key < node->key )
return search( node->left , key );
else // key > node->key
return search( node->right, key );
}
// 对以node为根的二叉搜索树进行前序遍历
void preOrder(Node* node) {
if( node != NULL ) {
cout<<node->key<<endl;
preOrder(node->left);
preOrder(node->right);
}
}
// 对以node为根的二叉搜索树进行中序遍历
void inOrder(Node* node) {
if( node != NULL ) {
inOrder(node->left);
cout<<node->key<<endl;
inOrder(node->right);
}
}
// 对以node为根的二叉搜索树进行后序遍历
void postOrder(Node* node) {
if( node != NULL ) {
postOrder(node->left);
postOrder(node->right);
cout<<node->key<<endl;
}
}
void destroy(Node* node) {
if( node != NULL ) {
destroy( node->left );
destroy( node->right );
delete node;
count --;
}
}
// 在以node为根的二叉搜索树中,返回最小键值的节点
Node* minimum(Node* node) {
if( node->left == NULL )
return node;
return minimum(node->left);
}
// 在以node为根的二叉搜索树中,返回最大键值的节点
Node* maximum(Node* node) {
if( node->right == NULL )
return node;
return maximum(node->right);
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
Node* removeMin(Node* node) {
if ( node->left == NULL ) {
Node* rightNode = node->right;
delete node;
count --;
return rightNode;
}
node->left = removeMin(node->left);
return node;
}
// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
Node* removeMax(Node* node) {
if ( node->right == NULL ) {
Node* leftNode = node->left;
delete node;
count --;
return leftNode;
}
node->right = removeMax(node->right);
return node;
}
// 删除掉以node为根的二分搜索树中键值为key的节点
// 返回删除节点后新的二分搜索树的根
Node* remove(Node* node, Key key) {
if ( node == NULL )
return NULL;
if ( key < node->key ){
node->left = remove( node->left , key );
return node;
}
else if ( key > node->key ){
node->right = remove( node->right, key );
return node;
}
else { // key == node->key
if( node->left == NULL ) {
Node *rightNode = node->right;
delete node;
count --;
return rightNode;
}
if ( node->right == NULL ) {
Node *leftNode = node->left;
delete node;
count--;
return leftNode;
}
// node->left != NULL && node->right != NULL
Node *successor = new Node(minimum(node->right));
count ++;
successor->right = removeMin(node->right);
successor->left = node->left;
delete node;
count --;
return successor;
}
}
};
|
