Instantly share code, notes, and snippets.

@smhanov /Heap.js
Last active Jun 27, 2018

Embed
What would you like to do?
// By Steve Hanov (2014)
// Released to public domain
//
// Minimum element is always on top.
// You can pass in an optional lessThan(a, b) function to the constructor.
// You may use .length to retrieve the length. Try not to set it though.
function Heap()
{
if (arguments.length) {
this.lessThan = arguments[0];
} else {
this.lessThan = function(a, b) {
return a < b;
};
}
this.length = 0;
this.A = [];
}
Heap.prototype = {
push: function(item) {
var A = this.A;
A.push(item);
var i = A.length-1;
while(i > 0 && !this.lessThan(A[i/2|0], A[i])) {
var temp = A[i/2|0];
A[i/2|0] = A[i];
A[i] = temp;
i = i/2|0;
}
this.length += 1;
},
pop: function() {
var A = this.A;
if (A.length === 0) {
return;
}
var max = A[0];
A[0] = A[A.length-1];
this._heapify(0);
A.length -= 1;
this.length -= 1;
return max;
},
_heapify: function(i) {
i += 1;
var l = 2 * i;
var r = 2 * i + 1;
var A = this.A;
var largest;
if (l <= A.length && this.lessThan(A[l-1], A[i-1])) {
largest = l;
} else {
largest = i;
}
if (r <= A.length && this.lessThan(A[r-1], A[largest-1])) {
largest = r;
}
if (largest !== i) {
var temp = A[i-1];
A[i-1] = A[largest-1];
A[largest-1] = temp;
this._heapify(largest-1);
}
}
};
Heap.test = function()
{
var heap = new Heap();
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";
}
};
/**
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.");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment