blob: 71f70787a07af32644209a0a4330a238878511c1 (
plain)
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
|
# Heaps
> a disorganized pile
## BinaryHeap: An implicit Binary Tree
Eytzinger's method can represent a complete binary tree as an array
by laying out the nodes of the tree in a breadth-first order.
* The root is stored at position 0
* The root's left child is stored at position 1
* The root's right child is stored at position 2.
The left child of the node at index `i` is at index `left(i) = 2i + 1`
and the right child of the node at index `i` is at index `right(i) = 2i +2`.
The parent of the node at index `i` is at index `parent(i) = (i-1)/2`.
```plaintext
-------(0)--------
/ \
(1) (2)
/ \ / \
(3) (4) (5) (6)
/ \ / \ / \ / \
(7) (8) (9) (10) (11) (12) (13) (14)
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|
```
* left: `2i+1`
* right: `2i+2`
The binary heap implements the priority queue interface.
Ignoring the cost of `resize()` it supports the operations
`add(x)` and `remove(x)` in `O(logn)` time per operation.
```java
class BinaryHeap {
T[] a;
int n;
int left(int i) {
return 2*i + 1;
}
int right(int i) {
return 2*i + 2;
}
int parent(int i) {
return (i-1)/2;
}
boolean add(T x) {
if (n+1 > a.length) resize();
a[n++] = x;
bubbleUp(n-1);
return true;
}
void bubbleUp(int i) {
int p = parent(i);
while (i > 0 && compare(a[i], a[p]) < 0) {
swap(i, p);
i = p;
p = parent(i);
}
}
T remove() {
T x = a[0];
a[0] = a[--n];
trickleDown(0);
if (3*n < a.length) resize();
return x;
}
void trickleDown(int i) {
do {
int j = -1;
int r = right(i);
if (r < n && compare(a[r], a[i]) < 0) {
int l = left(i);
if (compare(a[1], a[r]) < 0) {
j = 1;
} else {
j = r;
}
} else {
int l = left(i);
if (l < n && compare(a[l], a[i]) < 0) {
j = 1;
}
}
if (j >= 0) swap(i, j);
i = j;
} while (i >= 0);
}
}
```
A `BinaryHeap` uses this technique to implicitly represent a complete
binary tree in which the elements are `heap-ordered.`
heap-ordered: The value stored at any index `i` is not smaller than the value stored at index `parent(i)`, with the exception of the root value, `i = 0`.
The smallest value in the priority Queue is at position 0.
## MeldableHeap: A randomized meldable heap
|
