Created
May 14, 2022 13:39
-
-
Save jps/b072f9ba6a971f2bfb4b4623469e806e to your computer and use it in GitHub Desktop.
algo pratice typescript heap implementation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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