8000 ref: update `Heap` implementation (#237) · TheAlgorithms/TypeScript@e1f635a · GitHub
[go: up one dir, main page]

Skip to content

Commit e1f635a

Browse files
authored
ref: update Heap implementation (#237)
- Improved comments for clarity and correctness. - Used default parameter values where applicable for better readability. - Consistently used `void` return type for functions without a return value. - Ensured consistent use of semicolons for statement termination. - Made minor adjustments to ensure consistency in naming and coding style.
1 parent b4062be commit e1f635a

File tree

1 file changed

+22
-34
lines changed

1 file changed

+22
-34
lines changed

data_structures/heap/heap.ts

Lines changed: 22 additions & 34 deletions
151
Original file line numberDiff line numberDiff line change
@@ -3,14 +3,12 @@
33
* In a complete binary tree each level is filled before lower levels are added
44
* Each level is filled from left to right
55
*
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
77
*
8-
* The heap if often implemented using an array structure.
8+
* The heap is often implemented using an array structure.
99
* In the array implementation, the relationship between a parent index and its two children
1010
* are ((parentindex * 2) + 1) and ((parentindex * 2) + 2)
11-
*
1211
*/
13-
1412
export abstract class Heap<T> {
1513
protected heap: T[]
1614
// A comparison function. Returns true if a should be the parent of b.
@@ -23,17 +21,16 @@ export abstract class Heap<T> {
2321

2422
/**
2523
* 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
2926
*/
30-
private isRightlyPlaced(childIndex: number, parentIndex: number) {
27+
private isRightlyPlaced(childIndex: number, parentIndex: number): boolean {
3128
return this.compare(this.heap[parentIndex], this.heap[childIndex])
3229
}
3330

3431
/**
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
3734
*/
3835
private getChildIndexToSwap(
3936
leftChildIndex: number,
@@ -68,11 +65,11 @@ export abstract class Heap<T> {
6865
return this.size() === 0
6966
}
7067

71-
protected swap(a: number, b: number) {
68+
protected swap(a: number, b: number): void {
7269
;[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]]
7370
}
7471

75-
protected bubbleUp(index = this.size() - 1): void {
72+
protected bubbleUp(index: number = this.size() - 1): void {
7673
let parentIndex
7774

7875
while (index > 0) {
@@ -111,7 +108,7 @@ export abstract class Heap<T> {
111108
}
112109

113110
public check(): void {
114-
return this._check()
111+
this._check()
115112
}
116113

117114
private _check(index: number = 0): void {
@@ -122,41 +119,34 @@ export abstract class Heap<T> {
122119
if (
123120
this.heap[leftChildIndex] &&
124121
!this.isRightlyPlaced(leftChildIndex, index)
125-
)
122+
) {
126123
throw new Error('Heap does not adhere to heap invariant')
124+
}
127125

128126
if (
129127
this.heap[rightChildIndex] &&
130128
!this.isRightlyPlaced(rightChildIndex, index)
131-
)
129+
) {
132130
throw new Error('Heap does not adhere to heap invariant')
131+
}
133132

134133
this._check(leftChildIndex)
135134
this._check(rightChildIndex)
136135
}
137136
}
138137

139138
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) {
145140
super(compare)
146141
}
147142
}
148143

149144
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) {
155146
super(compare)
156147
}
157148
}
158149

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.
160150
export class PriorityQueue<T> extends MinHeap<T> {
161
// Maps from the n'th node to its index within the heap.
162152
private keys: number[]
@@ -166,38 +156,36 @@ export class PriorityQueue<T> extends MinHeap<T> {
166156
constructor(
167157
keys_index: (a: T) => number,
168158
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
172160
) {
173161
super(compare)
174162
this.keys = Array(num_keys).fill(-1)
175163
this.keys_index = keys_index
176164
}
177165

178-
protected swap(a: number, b: number) {
166+
protected swap(a: number, b: number): void {
179167
const akey = this.keys_index(this.heap[a])
180168
const bkey = this.keys_index(this.heap[b])
181169
;[this.keys[akey], this.keys[bkey]] = [this.keys[bkey], this.keys[akey]]
182170
super.swap(a, b)
183171
}
184172

185-
public insert(value: T) {
173+
public insert(value: T): void {
186174
this.keys[this.keys_index(value)] = this.size()
187175
super.insert(value)
188176
}
189177

190178
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.
192180
this.keys[this.keys_index(this.heap[0])] = -1
193181
if (this.size() > 1) {
194182
this.keys[this.keys_index(this.heap[this.size() - 1])] = 0
195183
}
196184
return super.extract()
197185
}
198186

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) {
201189
// If the key does not exist, insert the value.
202190
this.insert(value)
203191
return

0 commit comments

Comments
 (0)
0