fueanta

Binary Heap in TS

Jun 29th, 2021 (edited)
136
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. export enum HeapType {
  2.     Max, Min
  3. }
  4.  
  5. type HeapifyFn = {
  6.     (i: number): void;
  7. }
  8.  
  9. export class Heap<T> {
  10.     private _heap: T[];
  11.     private readonly _heapType: HeapType;
  12.     private readonly _heapifyFn: HeapifyFn;
  13.  
  14.     constructor(arr: T[] = [], heapType: HeapType = HeapType.Max) {
  15.         this._heap = [...arr];
  16.         this._heapType = heapType;
  17.  
  18.         if (heapType === HeapType.Max)
  19.             this._heapifyFn = this.maxHeapify;
  20.         else
  21.             this._heapifyFn = this.minHeapify;
  22.  
  23.         this.buildHeap(this._heapifyFn);
  24.     }
  25.  
  26.     private maxHeapify = (i: number = 0): void => {
  27.         const leftChildIndex = 2 * i + 1;
  28.         const rightChildIndex = 2 * i + 2;
  29.         let indexOfLargest = i;
  30.  
  31.         if ((leftChildIndex < this._heap.length) &&
  32.             (this._heap[leftChildIndex] > this._heap[indexOfLargest])
  33.         )
  34.             indexOfLargest = leftChildIndex;
  35.  
  36.         if ((rightChildIndex < this._heap.length) &&
  37.             (this._heap[rightChildIndex] > this._heap[indexOfLargest])
  38.         )
  39.             indexOfLargest = rightChildIndex;
  40.  
  41.         if (indexOfLargest != i) {
  42.             const temp = this._heap[i];
  43.             this._heap[i] = this._heap[indexOfLargest];
  44.             this._heap[indexOfLargest] = temp;
  45.  
  46.             this.maxHeapify(indexOfLargest);
  47.         }
  48.     }
  49.  
  50.     private minHeapify = (i: number = 0): void => {
  51.         const leftChildIndex = 2 * i + 1;
  52.         const rightChildIndex = 2 * i + 2;
  53.         let indexOfSmallest = i;
  54.  
  55.         if ((leftChildIndex < this._heap.length) &&
  56.             (this._heap[leftChildIndex] < this._heap[indexOfSmallest])
  57.         )
  58.             indexOfSmallest = leftChildIndex;
  59.  
  60.         if ((rightChildIndex < this._heap.length) &&
  61.             (this._heap[rightChildIndex] < this._heap[indexOfSmallest])
  62.         )
  63.             indexOfSmallest = rightChildIndex;
  64.  
  65.         if (indexOfSmallest != i) {
  66.             const temp = this._heap[i];
  67.             this._heap[i] = this._heap[indexOfSmallest];
  68.             this._heap[indexOfSmallest] = temp;
  69.  
  70.             this.minHeapify(indexOfSmallest);
  71.         }
  72.     }
  73.  
  74.     private buildHeap = (heapify: HeapifyFn): void => {
  75.         const heapSize = this._heap.length;
  76.  
  77.         if (heapSize > 1) {
  78.             const lastParent = ~~(heapSize / 2) - 1;
  79.  
  80.             for (let i = lastParent; i >= 0; --i) {
  81.                 heapify(i);
  82.             }
  83.         }
  84.     }
  85.  
  86.     public insert = (data: T): void => {
  87.         this._heap.push(data);
  88.  
  89.         let dataIndex = this._heap.length - 1;
  90.         let parentIndex = ~~((dataIndex - 1) / 2);
  91.  
  92.         if (this._heapType === HeapType.Max) {
  93.             while (parentIndex >= 0 && this._heap[dataIndex] > this._heap[parentIndex]) {
  94.                 const temp = this._heap[parentIndex];
  95.                 this._heap[parentIndex] = this._heap[dataIndex];
  96.                 this._heap[dataIndex] = temp;
  97.  
  98.                 dataIndex = parentIndex;
  99.                 parentIndex = ~~((dataIndex - 1) / 2);
  100.             }
  101.         }
  102.         else if (this._heapType === HeapType.Min) {
  103.             while (parentIndex >= 0 && this._heap[dataIndex] < this._heap[parentIndex]) {
  104.                 const temp = this._heap[parentIndex];
  105.                 this._heap[parentIndex] = this._heap[dataIndex];
  106.                 this._heap[dataIndex] = temp;
  107.  
  108.                 dataIndex = parentIndex;
  109.                 parentIndex = ~~((dataIndex - 1) / 2);
  110.             }
  111.         }
  112.     }
  113.  
  114.     public getRoot = (): T | null => this._heap.length ? this._heap[0] : null;
  115.  
  116.     public extractRoot = (): T | null => {
  117.         const root = this._heap.shift();
  118.         if (root) {
  119.             const lastEl = this._heap.pop();
  120.             if (lastEl) {
  121.                 this._heap.unshift(lastEl);
  122.                 this._heapifyFn(0);
  123.             }
  124.             return root;
  125.         }
  126.         else return null;
  127.     }
  128.  
  129.     public sort = (): T[] => {
  130.         const heapCopy: T[] = [...this._heap];
  131.         const sortedArr: T[] = [];
  132.  
  133.         while (this.getRoot()) {
  134.             const root = this.extractRoot();
  135.             if (root) sortedArr.push(root);
  136.         }
  137.  
  138.         this._heap = heapCopy;
  139.  
  140.         return sortedArr;
  141.     }
  142. }
  143.  
RAW Paste Data