|
/** |
|
By Steve Hanov. Released to the public domain 2018. |
|
|
|
This version is in typescript and also includes the ability to pop() from an arbitrary location in the heap. |
|
*/ |
|
|
|
export class Heap<T> { |
|
|
|
public length = 0; |
|
private A = new Array<T>(); |
|
|
|
constructor(private lessThan: (a:T,b:T) => boolean = null) { |
|
if (this.lessThan == null) { |
|
this.lessThan = function(a:T, b:T):boolean { |
|
return a < b; |
|
}; |
|
} |
|
} |
|
|
|
toSortedArray() { |
|
let a = this.A.concat(); |
|
a.sort( (a, b) => { |
|
return this.lessThan(a, b) ? -1 : 1; |
|
}); |
|
return a; |
|
} |
|
|
|
toArray() { |
|
return this.A.concat(); |
|
} |
|
|
|
heapify() { |
|
for(let i = this.A.length - 1; i >= 0; i--) { |
|
this.pushDown(i); |
|
} |
|
} |
|
|
|
clear() { |
|
this.length = 0; |
|
this.A.length = 0; |
|
} |
|
|
|
push(item:T) { |
|
this.pushUp(this.A.length, item); |
|
this.length += 1; |
|
} |
|
|
|
top():T { |
|
if (this.length) { |
|
return this.A[0]; |
|
} else { |
|
return null; |
|
} |
|
} |
|
|
|
pop(i:number = 0) { |
|
var A = this.A; |
|
if (A.length <= i) { |
|
return; |
|
} |
|
|
|
var max = A[i]; |
|
if (i === 0) { |
|
A[i] = A[A.length-1]; |
|
} else { |
|
i = this.pushUp(i, A[A.length-1]); |
|
} |
|
|
|
A.length -= 1; |
|
this.length -= 1; |
|
|
|
|
|
this.pushDown(i); |
|
|
|
|
|
return max; |
|
} |
|
|
|
get(i:number):T { |
|
return this.A[i]; |
|
} |
|
|
|
private pushUp(i:number, item:T) { |
|
let A = this.A; |
|
i += 1; |
|
|
|
while(i > 1 && !this.lessThan(A[(i/2|0)-1], item)) { |
|
A[i-1] = A[(i/2|0)-1]; |
|
i = i/2|0; |
|
} |
|
A[i-1] = item; |
|
return i-1; |
|
} |
|
|
|
private pushDown(i:number) { |
|
let A = this.A; |
|
i += 1; |
|
while(true) { |
|
let l = 2 * i; |
|
let r = 2 * i + 1; |
|
let smallest; |
|
if (l <= A.length && this.lessThan(A[l-1], A[i-1])) { |
|
smallest = l; |
|
} else { |
|
smallest = i; |
|
} |
|
|
|
if (r <= A.length && this.lessThan(A[r-1], A[smallest-1])) { |
|
smallest = r; |
|
} |
|
|
|
if (smallest === i) { |
|
break; |
|
} |
|
|
|
let temp = A[i-1]; |
|
A[i-1] = A[smallest-1]; |
|
A[smallest-1] = temp; |
|
i = smallest; |
|
} |
|
} |
|
|
|
static test() |
|
{ |
|
var heap = new Heap<number>(); |
|
heap.push(3); |
|
heap.push(2); |
|
heap.push(4); |
|
heap.push(1); |
|
heap.push(5); |
|
|
|
if (heap.pop() !== 1) { |
|
throw "Failed"; |
|
} |
|
|
|
if (heap.pop() !== 2) { |
|
throw "Failed"; |
|
|
|
} |
|
|
|
if (heap.pop() !== 3) { |
|
|
|
throw "Failed"; |
|
} |
|
|
|
if (heap.pop() !== 4) { |
|
throw "Failed"; |
|
|
|
} |
|
|
|
if (heap.pop() !== 5) { |
|
throw "Failed"; |
|
} |
|
|
|
function CheckHeap(heap) { |
|
let a = 0; |
|
while(heap.length) { |
|
let b = heap.pop(); |
|
if (a > b) { |
|
console.log("Heap error!"); |
|
console.log(heap.A); |
|
throw "Heap error"; |
|
} |
|
a = b; |
|
} |
|
} |
|
|
|
for (let j = 0; j < 1; j++) { |
|
|
|
for(let i = 0; i < 100; i++) { |
|
heap.push(Math.random()); |
|
} |
|
|
|
for(let i = 0; i < 20; i++) { |
|
let index = Math.floor(Math.random() * heap.length); |
|
heap.pop(index); |
|
} |
|
CheckHeap(heap); |
|
|
|
for(let i = 0; i < 100; i++) { |
|
heap.push(Math.random()); |
|
} |
|
|
|
Shuffle(heap.A); |
|
heap.heapify(); |
|
CheckHeap(heap); |
|
} |
|
|
|
console.log("Heap test passed."); |
|
} |
|
} |