×
Binary Tree,Max Heap, Priority Queue and implementation using Javascript


Binary Tree,Max Heap, Priority Queue and implementation using Javascript

June 9, 2018

Binary tree is a tree in which every node can have maximum of 2 children.In a binary tree data structure , every parent node can have at most two child nodes.Below is an example of a binary tree.

The node with value 100 is the root node.The value 50 and 20 are leaves.
A max-heap is a complete binary tree (every node has two children apart from leaves) in which the value in each  node is greater than or equal to the values in the children of that node. It means that the value of the root node will be the maximum.For a min heap the value at the root node should be the minimum. Below you can find example of a max-heap.
heap structure

The array representation of the above binary heap is given below.We start indexing from 1 and leave the 0th index.

 

As you can understand, for every node with index i ,the left child is having index 2i and the right child is having index 2i+1.The children are filled in from the left  . If we add another number 50 ,then it will be the child  of  14( 4th index).

So while on insertion , heap is rearranged so that it satisfies the heap property,ie 50 should be the root node
When are going to insert value 50
1 – Consider the element 50 to be  in the i th index (9th index).
2 – Now we take the floor of  i/2  (Floor – largest integer less than or equal to).In our case it is 4.
3-  Compare the value in  floor(i/2) to  the value in  i.If i th value is greater they are exchanged.See below
– In our case 50 is compared with 14
– 50 and 14 are exchanged
  The floor(i/2) becomes the new and the comparison is continued up  until the heap structure is correctly achieved.
– FInally 50 is compared with 40 ,they are exchanged that 50 becomes the root node and thus satisfy the max-heap structure.See the image below
Deleting the route node and keeping max-heap
This method is the most important and is called max heapify.
Deleting the route node is done in the following way
1 –  The root node is swapped with the last leaf node and the last leaf node is then deleted.
heap delete
2 – Now the current root node has the value from the last leaf.The root node has index i which is 1.The children of the node 2i and 2i+1 are compared with each other and compared with root node. They are swapped and process is repeated until max-heap structure is achieved.
 
The final heap structure is as follow
Priority Queue
 Priority queue can be efficiently implemented using Binary Heap.The following Javascript code gives you an implementation   of  priority queue using javascript
Consider a mailing system in which each mail id is given a priority

No Comments

Leave a Reply

Your email address will not be published. Required fields are marked *