Binary Heap

A Binary Heap is a Binary Tree that is kind of like an untidy collection, hence Heap, with that being said, it is still sorted in some type of way, specifically from low to high or high to low. For better clarification, we’ll call them Min Heap or Max Heap.

Max Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

Min Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

https://www.geeksforgeeks.org/heap-data-structure/

On the 3rd level, there is no actual distinct order

Creating a Class

A Tree will always have a root, which will act as the single parent with children in a hierarchical structure and each of these objects are called nodes.

That being said, lets make the Tree, and we’ll begin by creating an empty array to represent the system:

class BinaryHeap {
 constructor(){
 this.value = []
 }

Using an array we can then figure out each of the children positions by using 2n + 1 for the left child and 2n+2 for the right child.

So [0]’s left would be [1] and [0]’s right would be [2].

[1]’s left = [3], right =[4].

Assuming all nodes are completed and filled to as left as possible.

Sorting:

Lets create a method to help with sorting. For purpose of demonstration, we’ll use a Max Heap:

bubbleUp(arr) {
    let i = this.values.length - 1
    let parentI = Math.floor((i - 1)/2)
    while(this.values[parentI] < this.values[i]) {
      let tmp = this.values[parentI]
      this.values[parentI] = this.values[i]
      this.values[i] = tmp
    }
  }

Using a while condition, we swap if the value is less than the last element of the array.

.insert() method

With the helper method, we can then use it to sort the array to give us a vivid image of the tree:

insert(num) {
    // insert into next available spot
    // swap while node value is less than parent or if parent does not exist then node becomes root
    this.values.push(num)
    this.bubbleUp(this.values)  
}
let heap = new maxBinaryHeap
heap.insert(100)
heap.insert(40)
heap.insert(50)
heap.insert(10)
heap.insert(51)

100 would be inserted, then 40.

Since 40 is less than 100 it would become the left of the 100.

Upon inserting 50, since it is also less than 100, it would become the right of the 100.

We now enter 10, and it will become the new last element [3], we will compare it with Math.floor([(i-2)/2)]), which in this case is [1].

The parent index is now 1 instead of 0, since it does not have any children, it will fill the position as long as the value is not greater than its parent index.

arr = [100, 40, 50, 10]

Now lets fill in 51, it becomes the new last element of the array-[4], we will now again compare it with Math.floor([(i-2)/2)]), which will be [1].

Since 51 > 40, it is greater than its parent index, we will actually now swap it with its parent.

the array now looks like this:

arr = [100, 51, 50, 40, 10]

Conclusion

The important thing to to notice is that for as long as there is an empty position, the node could be filled and as siblings, there’s no actual discrimination for as long as its parent isn’t greater or less than its children depending on the type of the heap, and there you have it, binary heap.

Thanks for reading!