3
3
* In a complete binary tree each level is filled before lower levels are added
4
4
* Each level is filled from left to right
5
5
*
6
- * In a (min|max) heap the value of every node is (less|greater) than that if its children
6
+ * In a (min|max) heap the value of every node is (less|greater) than that of its children
7
7
*
8
- * The heap if often implemented using an array structure.
8
+ * The heap is often implemented using an array structure.
9
9
* In the array implementation, the relationship between a parent index and its two children
10
10
* are ((parentindex * 2) + 1) and ((parentindex * 2) + 2)
11
- *
12
11
*/
13
-
14
12
export abstract class Heap < T > {
15
13
protected heap : T [ ]
16
14
// A comparison function. Returns true if a should be the parent of b.
@@ -23,17 +21,16 @@ export abstract class Heap<T> {
23
21
24
22
/**
25
23
* Compares the value at parentIndex with the value at childIndex
26
- * In a maxHeap the value at parentIndex should be larger than the value at childIndex
27
- * In a minHeap the value at parentIndex should be smaller than the value at childIndex
28
- *
24
+ * In a maxHeap, the value at parentIndex should be larger than the value at childIndex
25
+ * In a minHeap, the value at parentIndex should be smaller than the value at childIndex
29
26
*/
30
- private isRightlyPlaced ( childIndex : number , parentIndex : number ) {
27
+ private isRightlyPlaced ( childIndex : number , parentIndex : number ) : boolean {
31
28
return this . compare ( this . heap [ parentIndex ] , this . heap [ childIndex ] )
32
29
}
33
30
34
31
/**
35
- * In a maxHeap the index with the larger value is returned
36
- * In a minHeap the index with the smaller value is returned
32
+ * In a maxHeap, the index with the larger value is returned
33
+ * In a minHeap, the index with the smaller value is returned
37
34
*/
38
35
private getChildIndexToSwap (
39
36
leftChildIndex : number ,
@@ -68,11 +65,11 @@ export abstract class Heap<T> {
68
65
return this . size ( ) === 0
69
66
}
70
67
71
- protected swap ( a : number , b : number ) {
68
+ protected swap ( a : number , b : number ) : void {
72
69
; [ this . heap [ a ] , this . heap [ b ] ] = [ this . heap [ b ] , this . heap [ a ] ]
73
70
}
74
71
75
- protected bubbleUp ( index = this . size ( ) - 1 ) : void {
72
+ protected bubbleUp ( index : number = this . size ( ) - 1 ) : void {
76
73
let parentIndex
77
74
78
75
while ( index > 0 ) {
@@ -111,7 +108,7 @@ export abstract class Heap<T> {
111
108
}
112
109
113
110
public check ( ) : void {
114
- return this . _check ( )
111
+ this . _check ( )
115
112
}
116
113
117
114
private _check ( index : number = 0 ) : void {
@@ -122,41 +119,34 @@ export abstract class Heap<T> {
122
119
if (
123
120
this . heap [ leftChildIndex ] &&
124
121
! this . isRightlyPlaced ( leftChildIndex , index )
125
- )
122
+ ) {
126
123
throw new Error ( 'Heap does not adhere to heap invariant' )
124
+ }
127
125
128
126
if (
129
127
this . heap [ rightChildIndex ] &&
130
128
! this . isRightlyPlaced ( rightChildIndex , index )
131
- )
129
+ ) {
132
130
throw new Error ( 'Heap does not adhere to heap invariant' )
131
+ }
133
132
134
133
this . _check ( leftChildIndex )
135
134
this . _check ( rightChildIndex )
136
135
}
137
136
}
138
137
139
138
export class MinHeap < T > extends Heap < T > {
140
- constructor (
141
- compare = ( a : T , b : T ) => {
142
- return a < b
143
- }
144
- ) {
139
+ constructor ( compare : ( a : T , b : T ) => boolean = ( a : T , b : T ) => a < b ) {
145
140
super ( compare )
146
141
}
147
142
}
148
143
149
144
export class MaxHeap < T > extends Heap < T > {
150
- constructor (
151
- compare = ( a : T , b : T ) => {
152
- return a > b
153
- }
154
- ) {
145
+ constructor ( compare : ( a : T , b : T ) => boolean = ( a : T , b : T ) => a > b ) {
155
146
super ( compare )
156
147
}
157
148
}
158
149
159
- // Priority queue that supports increasePriority() in O(log(n)). The limitation is that there can only be a single element for each key, and the max number or keys must be specified at heap construction. Most of the functions are wrappers around MinHeap functions and update the keys array.
160
150
export class PriorityQueue < T > extends MinHeap < T > {
161
151
// Maps from the n'th node to its index within the heap.
162
152
private keys : number [ ]
@@ -166,38 +156,36 @@ export class PriorityQueue<T> extends MinHeap<T> {
166
156
constructor (
167
157
keys_index : ( a : T ) => number ,
168
158
num_keys : number ,
169
- compare = ( a : T , b : T ) => {
170
- return a < b
171
- }
159
+ compare : ( a : T , b : T ) => boolean = ( a : T , b : T ) => a < b
172
160
) {
173
161
super ( compare )
174
162
this . keys = Array ( num_keys ) . fill ( - 1 )
175
163
this . keys_index = keys_index
176
164
}
177
165
178
- protected swap ( a : number , b : number ) {
166
+ protected swap ( a : number , b : number ) : void {
179
167
const akey = this . keys_index ( this . heap [ a ] )
180
168
const bkey = this . keys_index ( this . heap [ b ] )
181
169
; [ this . keys [ akey ] , this . keys [ bkey ] ] = [ this . keys [ bkey ] , this . keys [ akey ] ]
182
170
super . swap ( a , b )
183
171
}
184
172
185
- public insert ( value : T ) {
173
+ public insert ( value : T ) : void {
186
174
this . keys [ this . keys_index ( value ) ] = this . size ( )
187
175
super . insert ( value )
188
176
}
189
177
190
178
public extract ( ) : T {
191
- // Unmark the the highest priority element and set key to zero for the last element in the heap.
179
+ // Unmark the highest priority element and set key to zero for the last element in the heap.
192
180
this . keys [ this . keys_index ( this . heap [ 0 ] ) ] = - 1
193
181
if ( this . size ( ) > 1 ) {
194
182
this . keys [ this . keys_index ( this . heap [ this . size ( ) - 1 ] ) ] = 0
195
183
}
196
184
return super . extract ( )
197
185
}
198
186
199
- public increasePriority ( idx : number , value : T ) {
200
- if ( this . keys [ idx ] == - 1 ) {
187
+ public increasePriority ( idx : number , value : T ) : void {
188
+ if ( this . keys [ idx ] === - 1 ) {
201
189
// If the key does not exist, insert the value.
202
190
this . insert ( value )
203
191
return
0 commit comments