Skip to content

Instantly share code, notes, and snippets.

@jps
Created May 14, 2022 13:39
Show Gist options
  • Select an option

  • Save jps/b072f9ba6a971f2bfb4b4623469e806e to your computer and use it in GitHub Desktop.

Select an option

Save jps/b072f9ba6a971f2bfb4b4623469e806e to your computer and use it in GitHub Desktop.
algo pratice typescript heap implementation
const assert = require('assert');
//i = item index
//left child index = 2i +1
//right child index = 2i +2
const heapPush = (heap:Array<number>, value: number) => {
heap.push(value)
let index = heap.length-1;
while(index > 0)
{
let parentIndex = Math.floor((index-1)/2);
let parent = heap[parentIndex];
let current = heap[index];
if(current >= parent)
{
break; //heap is stable
}
heap[parentIndex] = current;
heap[index] = parent;
index = parentIndex;
}
return heap;
}
assert.deepStrictEqual(heapPush([], 1), [1]);
assert.deepStrictEqual(heapPush([1], 2), [1,2]);
assert.deepStrictEqual(heapPush([2], 1), [1,2]);
assert.deepStrictEqual(heapPush([2,3,4,5,6,7,8,9], 1), [1,2,4,3,6,7,8,9,5]);
const heapPop = (heap:Array<number>) : number | undefined => {
if(heap.length === 0)
{
return;
}
if(heap.length === 1)
{
return heap.pop();
}
//swap first and last and remove
const lastIndex = heap.length-1;
[heap[0], heap[lastIndex]] = [heap[lastIndex], heap[0]]
let poppedElement = heap.pop();
//swap root element until the heap property is satisfied
let index = 0;
while(true)
{
let leftIndex = (index*2)+1;
let rightIndex = (index*2)+2;
//we are on a leaf
if(leftIndex > heap.length && rightIndex > heap.length)
{
break;
}
let leftChild = heap[leftIndex];
let rightChild = heap[rightIndex];
let leftIsLess = leftChild < heap[index];
let rightIsLess = rightChild < heap[index];
//heap property satisfied
if(!leftIsLess && !rightIsLess)
{
break;
}
//swap left
if(leftChild < rightChild || leftIsLess)
{
[heap[index], heap[leftIndex]] = [heap[leftIndex], heap[index]];
index = leftIndex;
}
//swap right
else{
[heap[index], heap[rightIndex]] = [heap[rightIndex], heap[index]];
index = rightIndex;
}
}
return poppedElement;
}
assert.equal(heapPop([]), undefined);
assert.equal(heapPop([1]), 1);
let testArray = [1,2];
assert.equal(heapPop(testArray), 1);
assert.deepStrictEqual(testArray, [2])
testArray = [1,2,3,4,5,6];
assert.equal(heapPop(testArray), 1);
assert.deepStrictEqual(testArray, [2,4,3,6,5]);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment