A binary Heap is a tree structure it is compact as possible, all the children of the node are as full as they can and the left children are filled first.

Type of Binary Heap

• Max Binary Heap

• Min Binary Heap

Max Binay Heap its parent node is always larger than its child node at every level down the tree.

Min Binary Heap its parent node is always smaller than its child node at every level down the tree.

Why heap

Binary heaps are used to implement priority queues and it's a very common data structure they are also used with graph traversal algorithms.

Storing Heap

lis and array are commonly used to store heap which is a built in data structure for any programming language.

Storing heap as a List

Storing Heap as an array

therefore, for any index "n" inside of an array, the left child node is stored at (2n+1) while its right child node is stored at (2n+2).

For example below array when its parent is at index "3" we found its left child by multiplying 3 by 2 and then adding 1 to it which gives "7" (2n +1) and then we found its right child by multiplying the parent index by 2 and then add 2 to which gives "8" (3*2+2) 2n +2

Insert to a Max Binary Heap.

The process of inserting something to a Binary heap is to fill out from left to an array, which basically pushes to the array and we then do something to the new value of the array which is called bubbling up what that means is to swap it until we find its correct resting place in the array, in max Binary Heap the large value is going to bubble up to the correct spot and then do a comparison.

Pushing "55" to an array, by putting it there its index means it is a child of "33" with this (n-1)/2 reversing the previous operation and "33" is index of "2" and its children are index "5" and "6" so next bubble up which is to compare "55" to its parent then swap because "55" is larger.

class MaxBinaryHeap {
    constructor() {
        this.val = []
    }
    insert(element) {
        this.val.push(element)
        this.bubbleUp()
    }
    bubbleUp() {
        let index = this.val.length - 1
        const element = this.val[index]
        while (index > 0) {
            let parentIdx = Math.floor((index - 1) / 2)
            let parent = this.val[parentIdx]
            if (element <= parent) break
            if(element > parent){ 
                this.val[parentIdx] = element
                this.val[index] = parent
            }
            index = parentIdx
        }
    }
}
// [41,39,33,18,27,12,55]
//  0  1  2  3  4  5  6

Big O of Binary heap

For insertion, the time complexity is O(logn) which is basically O(log base 2 to n)

each time we go down a step in binary structure we have 2 times the number of nodes

Suppose we wanted to insert '200' to this Binary heap, this is worst case because it is the largest number and it is going to end up at the starting point of this Binary queue. We only have to compare it one time per step therefore for 16 elements there are 4 comparisons which is 2 to what power gives 16 === 4 (2*2*2*2) however It's the same Idea for removal O(logn) as well.