### Heap Data Structure

// Binary heap is a partially ordered binary tree // which satisfies the heap property | |

// each node has at most two child nodes | |

// | |

// heap property indicates specific relationship between parent | |

// and child notes. | |

// | |

// --- Heap Property --- | |

// max heap: all parent nodes are greater than or equal to child node | |

// min heap: all parent nodes are less than or equal to child node | |

// order between child nodes on the same level does not matter, only parent-child | |

// | |

// binary heap trees are balanced trees, i.e. all levels of tree are fully filled | |

// and if last level is partially filled, its filled from left to right | |

// | |

// heaps can be implemented as arrays, possible because of partial ordering according | |

// to the heap property. | |

// | |

// index of elements in arrays follow this formula: | |

// left child: i * 2 | |

// right child: i * 2 + 1 | |

// parent: floor(i / 2); round down to nearest number | |

// | |

// heap arrays do NOT have index 0; they start at 1 | |

// last index is also size of heap because heaps start at index 0 | |

let MinHeap = function() { | |

let heap = [null]; // set index 0 to null b/c root starts at index 1 | |

this.insert = function(num) { | |

heap.push(num); // first add number to end of heap array, then reorder | |

// heap.length > 2; means there's more than 1 element in heap | |

// if that's the case we need to reorder after adding element to end of arr | |

if (heap.length > 2) { | |

// index of last element | |

let index = heap.length - 1; | |

// Math.floor(index/2) is equation for index of parent node | |

// this says while last element is less than its parent | |

while (heap[index] < heap[Math.floor(index/2)]) { | |

// if index isn't 0, i.e. if we haven't reached the root node | |

if (index >= 1) { | |

// switch the location of parent and child within the array | |

[heap[Math.floor(index/2)], heap[index]] = [heap[index], heap[Math.floor(index/2)]]; | |

// if parent node is not root node; root node index is 1 | |

if (Math.floor(index/2) > 1) { | |

// set index pointer to parent and repeat while loop | |

// to continue comparing parent and child | |

index = Math.floor(index/2); | |

// else if parent node is root node break out of while loop | |

} else { | |

break; | |

} | |

} | |

} | |

} | |

} | |

this.remove = function() { | |

// we always remove root node from heap | |

let smallest = heap[1]; | |

// if we have more than one node in tree | |

if (heap.length > 2) { | |

// set the first node to be the last node | |

heap[1] = heap[heap.length - 1]; | |

// remove the last element from the array | |

// since we already moved it to first index | |

heap.splice(heap.length - 1); | |

// if length is 3 there's only 2 numbers within tree, (0 index is null) | |

if (heap.length == 3) { | |

// move the smallest element to index 1 | |

if (heap[1] > heap[2]) { | |

[heap[1], heap[2]] = [heap[2], heap[1]]; | |

} | |

return smallest; | |

} | |

// if above conditional did not return then there are more than | |

// 2 elements in heap so it's more complicated | |

let i = 1; | |

let left = 2 * i; | |

let right = 2 * i + 1; | |

// while root element is greater than or equal to left or right child | |

while (heap[i] >= heap[left] || heap[i] >= heap[right]) { | |

if (heap[left] < heap[right]) { | |

// if left child is smallest of 3, switch it with root | |

[heap[i], heap[left]] = [heap[left], heap[i]]; | |

// move index pointer to next left child and repeat while loop | |

i = 2 * i; | |

} else { | |

// right child must be smallest of 3, switch it with root | |

[heap[i], heap[right]] = [heap[right], heap[i]]; | |

// move index pointer to next right child and repeat while loop | |

i = 2 * i + 1; | |

} | |

// update new left and right indexes | |

left = 2 * i; | |

right = 2 * i + 1; | |

if (heap[left] == undefined || heap[right] == undefined) { | |

// if left or right child nodes are undefined we're at bottom of tree | |

// so break out of while loop | |

break; | |

} | |

} | |

} else if (heap.length == 2) { | |

// if heap just has one element just cut off that element | |

// if just one element length of heap is 2 because index 0 is null | |

heap.splice(1, 1); | |

} else { | |

// otherwise tree is empty, return null | |

return null; | |

} | |

return smallest; | |

} | |

// common use case for heap data structure is for heap sort | |

// this is one of most efficient sorting algorithms with | |

// average and worst case performance of O(n logn) | |

// | |

// Heap sort takes an unsorted array, adding each item in the array | |

// into a min heap, and then extracting every item out of the min | |

// heap into a new array | |

// | |

// the min heap structure ensures that the new array will contain | |

// the original items in least to greatest order | |

this.sort = function() { | |

let result = new Array(); | |

while (heap.length > 1) { | |

// push smallest element from heap array | |

// onto this new array until heap length is 1, i.e. heap is empty | |

// remove() will return elements of heap in order | |

// so results array will contain all elements in min order | |

result.push(this.remove()); | |

} | |

return result; | |

} | |

} | |

var myHeap = new MinHeap(); | |

myHeap.insert(3); |