What are Heaps? Priority Queue | Real World Usage Like NewsFeed Design

Binary tree, Binary search tree, full and complete binary tree we can combine these ideas together so that we can learn a new assistant data structure which is HEAP.

From heap, we can learn about priority queue which is a variation on the queue data structure and is much more helpful .

Before understanding what is heap?

Let's first understand why do we need heap?

We use heap every day, using facebook, instagram, linkedin , youtube

every thing organizes data based on a priority. For example, facebook might show you the top post that matched your profile based preferences, or videos that has maximum retention rate.

Heaps by design is a data structure that resembles a binary tree. In particular it resembles complete binary tree.

Lookup => O(N)
Insert. => O(logN)
Delete => O(logN)

Heap can be used in any algorithm where ordering is important.

With array, we have random access, it allowed us to randomly access any element using index. In linked list, we can change things dynamically, but finding a node is linear time of O(N).

Heaps are little bit different, compared to binary search tree, look up takes more time but what's effective?

Why use binary heap?

Binary heaps are really really great at doing comparative operation.

					101
            72                33
        2     45           5     1

Get all values greater than 33?

Grab the upper level items instead of going down for finding it. Whereas in binary search tree it is O(N).

A complete binary tree are ones where every single level is full expect for the very last level. But if there are nodes in the last level it must be pushed to the left as possible.

Two Variations on Heap:

Max Heap

• Has values in such a way, at every single node all of the children of that node are smaller than it.

        50
    40	    25
20.   35. 10.   15

Keeping these rules in mind, the main thing to focus on is that the root node of a max heap is the greatest value in this entire heap.

Then, nodes i.e child of the parent node are the second and third greatest values inside of this heap?

No this is not the case!

Min Heap:

• Min heap is just the reverse of this rule, meaning that the root node is the smallest value inside the heap. Similarly all of the values that are children to this node must be greater than this root value.
• Root node of the min heap is the smallest value of this data structure.

How to Add & Remove values from Heap?

How to represent a heap inside the code?

Up until now, working with binary tree, we get the root node as an object.

Another way to represent binary tree is an array!

Using BFS we fill the value in the array.

Heap:
               50
             /    \
          40        25
         /  \      /  \
        20  35    10  15    

array = [50 , 40 , 25, 20, 35, 10, 15]
         0     1.  2.   3. 4.   5. 6

Only difference between array and object of tree node is that using array we need to figure out some mathematical formula that help us define the relationship between nodes.

Think about the relationship related to indices of the values inside our array.

Mathematical Relationships:

               50
             /    \
          40        25
         /  \      /  \
        20  35    10  15   

1. Parent Node:

To get the parent of any node

Math.floor (( index -1 ) / 2)

10 has index of 5, using this formula

Math.floor((5 - 1) / 2) = 2
25 is the parent node of 2. 

2. Left Child:

To get the left child of any node

(Index * 2) + 1

let's find the left chid of 40, 40 has index 1

(1 * 2) + 1 = 3
@index 3 we have 20

3. Right Child

To get the right child of any node

(Index * 2) + 2

let's find the right child of 40, index = 1

1 * 2 + 2 = 4
@ index 4, we have 35

Insertion:

Insert 45

               50
             /    \
          40        25
         /  \      /  \
        20  35    10  15   

The only way we can insert 45 is at the next available sport. Following BFS order

               50
             /    \
          40        25
         /  \      /  \
        20  35    10  15   
      /
    45

First we insert, the 45 in, we look at the total structure and ask if this is still a valid max heap?

Not it's not!

20 < 45 , and also 45 is greater than 40.

We need to rearrange our max heap.

How do we Rearrange?

Steps to Follow:

1. Take 45 and it's immediate parent i.e 20, then compare, is 45 greater than 20?

• yes, so swap it

               50
             /    \
          40        25
         /  \      /  \
        45  35    10  15   
      /
    20

2. Again, compare the new parent i.e (45) greather than it's immediate parent i.e (40)?

• yes, so swap it again!

               50
             /    \
          45        25
         /  \      /  \
        40  35    10  15   
      /
    20

3. Then compare again, is 45 greater than 50?

• No, so no swap is needed.

Thus our heap is valid and new final heap.

**************** With Array********************

               50
             /    \
          40        25
         /  \      /  \
        20  35    10  15    

    [50, 45, 25,  20, 35, 10, 15]
      0   1   2   3   4   5    6

In the exact same vein, what we need to do, we just insert 45 at the end of an array.

array.push(45)

               50
             /    \
          40        25
         /  \      /  \
        20  35    10  15    
       /
     45

1. Compare new value i.e 45 with it's immediate parent value and keep comparing and swapping value until find it's final resting point.

• we get the index of 45 i.e 7
• parent is given by formula Math.floor(index - 1)/2)
• Math.floor( (7 -1) / 2 ) = 3

@ position 3 , we have 20, which is the parent of 45.

Now we ask if 45 greater than 20?

if so we swap it

              *               #
 [50, 40, 25, 45, 35, 10, 15, 20]
  0   1   2   3   4   5   6   7

2. Then we compare again,

• we take index 3, find it's parent i.e Math.floor((index-1)/2) = 1

  @ position 1, we have 40,  is 40 < 45 ?

yes. so swap once again

           *       #
      [50, 45, 25, 40, 35, 10, 15, 20]
       0   1   2   3   4   5   6   7     

3. Compare one more time,

• index = 1, parentNode = Math.floor((index -1)/2) = 0

 @ position 0, we have 50

is 50 < 45 ?

No

Thus the final resting point

Now, what about removing the nodes from Heap?

The reason why we implement the heap, particularly max heap is: we supply values, & whenever we want to retrieve a value , it has to give the greatest value amongst the value we supplied.

So this is why max heap, whenever we talk about removal, deletion or retrieving a value form this heap, the only condition we want to satisfy is that we are getting the greatest value, which is root value in max heap.

              75
             /    \
          50        25
        /   \      /  \
       45    35    10  15   
     /   \
    20    40

 

let call remove here, which will remove the 75 and return it

               ()
             /    \
          50        25
        /   \      /  \
       45    35    10  15   
     /   \
    20    40

Now we need to restructure our heap so we can maintain not only the rule that the max heap has greatest value at the top of the tree, but also it is still a complete binary tree.

Procedure to remove:

1. We are going to take the right most value at the last level as placeholder root

               40
             /    \
          50        25
        /   \      /  \
       45    35    10  15   
     /   
    20    

Here the root value is not the greatest value, so we need to shift this value down. How???

2. Starting from the root value, it's two children. Which one is greater value?

• Left or right? i.e 50 or 25?
• 50, which is left. Is this also greater than it's root value?
• Yes!!!, so swap it to the root

              50
            /    \
          40        25
        /   \      /  \
       45    35    10  15   
     /   
    20    

3. Do the same iteration with 40 again, amongst it's children which one is greater?

• left or right? i.e 45 or 35?
• 45, which is left. Is this also greater than it's root value (40)?
• Yesss!!, so swap it with immediate parent.

              50
             /    \
          45        25
        /   \      /  \
       40    35    10  15   
     /   
    20    

4. Once again, we going to say does 49 has two children?

• No it has 1,
• let's take that child and compare it with parent, is 20 greater than 40?

No!!!

So now we know 40 is at it's final resting point.

Now we see that 50 is the greatest value inside the max heap once again.

**************** With Array********************

              75
             /    \
          50        25
        /   \      /  \
       45    35    10  15   
     /   \
    20    40

 [75, 50, 25, 45, 35,  10, 15, 20, 40]
  0   1   2   3   4     5  6   7    8

How to remove an item from max heap?

1. Remove 75, and push 40 in it's place

    [40, 50, 25, 45, 35,  10, 15, 20]. 
      0   1   2   3   4    5   6  7 

                40
              /    \
            50        25
          /   \      /  \
        45    35    10  15   
      /   
      20    

2. Now let's compare and find the correct place of our new value.

• We take left and right child of 40 i.e @ index 0
• left = (2 * index) + 1 = 1 i.e array[1] = 50
• right = (2 * index) + 2 = 2 i.e array[2] = 25

since 25 < 50. and 50 is also greater than 40, so we swap our position

    [50, 40, 25, 45, 35,  10, 15, 20]. 
      0   1   2   3   4    5   6  7 

                50
              /    \
            40        25
          /   \      /  \
        45    35    10  15   
      /   
      20    

3. Once again , we take 40 @ index 1 and find it's two children

• left = (2*1) + 1 = 3 , array[3] = 45
• right = (2*1) + 2 = 4 , array[4] = 35

since 35 < 45 and parent i.e (40) < 45, we swap it

    [50, 45, 25, 40, 35,  10, 15, 20]. 
      0   1   2   3   4    5   6  7 

                50
              /    \
            45        25
          /   \      /  \
        40    35    10  15   
      /   
    20  

4. Once again we take 40 @ position 3, we get it's child

• left = (2 * index) + 1 = 2*3 +1 = 7, array[7] =20
• right = (2 * index) + 2 = undefined

since 20 < 40, we don't perform swap.

 /*
    functions to implement on pq:
    1. insert
    2. remove
    3. peek
    4. size
    5. isEmpty
    
    1. _leftChild
    2. rightChild
    3. _parent
    4. _swap
    5. _bubbleUp
    6. _bubbleDown

*/

class PQ{
    constructor(comparator){
        this.compare = comparator
        this.heap = []
    }
    _leftChild(index){
        return (index * 2) + 1
    }

    _rightChild(index){
        return (index * 2) + 2
    }
    
    _parent(index){
        return (index - 1) / 2
    }
    _swap(i, j){
        let temp = this.heap[i]
        this.heap[i] = this.heap[j]
        this.heap[j] = temp
    }
    _compare(i, j){
        return this.heap[i] > this.heap[j]
    }

//for insertion
_bubbleUp(){
let addedItemIdx = this.size() - 1
while(this._compare(this._parent(addedItemIdx), addedItemIdx)){
     this._swap( addedItemIdx, this._parent(addedItemIdx))
     addedItemIdx = this._parent(addedItemIdx)
}
}

// for deletion
_bubbleDown(){
let nodeIdx = 0
while(  0 < this._leftChild(nodeIdx)  
&& this._compare(this._leftChild(nodeIdx), nodeIdx) 
|| 0 < this._rightChild(nodeIdx) 
&& this._compare(this._rightChild(nodeIdx), nodeIdx)){

if right child exist, left child must exist

but if the left child exist we don't know if right child exist

if right child exist we check if it's greater than left child,

if at any point right child doesn't exist we know left is greater

let greaterIdx = this.rightChildIdx(nodeIdx) 
&& this._compare( this._rightChild(nodeIdx),      
   this._leftChild(nodeIdx)) 
  ? this._rightChild(nodeIdx) 
  : this._leftChild(nodeIdx)
           
 this._swap(greaterIdx, nodeIdx)
            nodeIdx = greaterIdx
 }
}

    isEmpty(){
        return this.heap.length === 0
    }
    size(){
        return this.heap.length 
    }
    insert(value){
        // if(this.isEmpty()){}
        this.heap.push(value)
        this._bubbleUp()
        return true
    }

    removal(){
        // need to remove the top elememnt
        // for that pop will not work
        // swap 1st and last elem
        // and pop out the last one and return it


        if(this.size() > 1){
            this._swap(0, this.size - 1 )
        }
        const poppedVal = this.heap.pop()
        this._bubbleDown()
        return poppedVal
    }
    peek(){
        return this.heap[0]
    }
}

#dataStructures #algorithm #systemDesign #NewsFeed #javascript