Skip to content

Instantly share code, notes, and snippets.

@smhanov 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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.