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.

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

1 |
[ null, 40, 20, 15, 14, 12, 10, 9 , 8 ] |

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).

1 |
[ null, 40, 20, 15, 14, 12, 10, 9 , 8,50] |

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**i**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.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
class maxHeap { constructor(array) { this.array = [null, ...array]; this.size = array.length } arrange(idx) { while (idx > 1 && this.compare(Math.floor(idx / 2), idx)) { this.swap(idx, Math.floor(idx / 2)); idx = Math.floor(idx / 2); } } heaper(idx1) { while (2 * idx1 <= this.size) { let idx2 = 2 * idx1; if (idx2 < this.size && this.compare(idx2, idx2 + 1)) idx2++; if (!this.compare(idx1, idx2)) break; this.swap(idx1, idx2); idx1 = idx2; } } rootdelete() { let max = this.array[1] this.swap(1, this.size--); this.heaper(1); this.array[this.size + 1] = null; return max; } insert(element) { this.array[++this.size] = element; this.arrange(this.size); } compare(idx1, idx2) { return this.array[idx1].priority < this.array[idx2].priority; } swap(idx1, idx2) { const temp = this.array[idx1]; this.array[idx1] = this.array[idx2]; this.array[idx2] = temp; } returnall() { return this.array; } } let newvar = new maxHeap([]); newvar.insert({name:'1@gmail.com',priority:20}); newvar.insert({name:'2@gmail.com',priority:10}); newvar.insert({name:'3@gmail.com',priority:30}); newvar.insert({name:'4@gmail.com',priority:50}); newvar.insert({name:'5@gmail.com',priority:40}); let resultarra = newvar.returnall() console.log(resultarra); |

1 2 3 |
//Response [ null, { name: '4@gmail.com', priority: 50 },{ name: '5@gmail.com', priority: 40 }, { name: '1@gmail.com', priority: 20 },{ name: '2@gmail.com', priority: 10 },{ name: '3@gmail.com', priority: 30 } ] |

## No Comments