CS 310 Heaps, Page 1'&$%HeapsNot the heap we discuss in the context of C++.A heap is a complete binary tree such that each node in the tree isgreater than or equal to all its children/descendents.917769 34611527769 346117769 3461191CS 310 Heaps, Page 2'&$%Adding An Entry to A Heap4535 232719 521 22 4Add 424535 232719 521 22 4424535 232719 5 2122 4424535232719 5 2122 44242 < 45, stop42 > 21, swap them42 > 35, swap themCS 310 Heaps, Page 3'&$%Pseudocode for Adding An EntryStep-1. Place the new entry in the heap in the first availablelocation.• How do we find that location ?Step-2. Swap the new entry with its parent until the new entry issmaller than or equal to its parent.CS 310 Heaps, Page 4'&$%Removing The Largest from A Heap4535232719 5 2122 442pomote35232719 52122 44221 < max(children of 21),swap 21 and 4235232719 52122 44221 < max(children of 21),swap 21 and 3535 232719 521 22 442CS 310 Heaps, Page 5'&$%Pseudocode for Removing The LargestStep-1. Copy the last entry in the deepest level to the root, anddelete this last node. This entry is called the “out-of-place”entry.Step-2. Swap the out-of-place entry with its largest child until it isgreater than both of its children.How do we find the last entry in the deepest level ?CS 310 Heaps, Page 6'&$%Array Representation of Complete Binary Trees4535232719 5 2122 44245 422327 3522 4195210 1 2 3 4 5 6 7 8 9Level 2Level 3 Level 4Level 1CS 310 Heaps, Page 7'&$%FormulaGiven a tree node stored as the i-th element of the array,• its parent is stored at location (i − 1)/2, using integer division• its left child is stored at location 2i + 1, and• its right child is stored at location 2i + 2.In the insert() and remove() methods, how do you find the lastentry in the deepest level ?CS 310 Heaps, Page 8'&$%Class Declaration of Heapstemplate <class T>class Heap {public:Heap (); ~Heap();void insert (T& entry);void remove_largest (T& largest);private:static const int MAXIMUM = 1000;int data_count;T data[MAXIMUM];};You may want to use dynamic arrays to remove the capacitylimitation of this implementation.CS 310 Heaps, Page 9'&$%Implementing The insert() Methodtemplate <class T>void Heap::insert (T& entry){}CS 310 Heaps, Page 10'&$%Applications of HeapsApplication 1: Priority Queues• A priority queue is a data structure that stores entries alongwith a priority for each entry.• Entries are removed in order of priorities — the highestpriority entry is removed first.CS 310 Heaps, Page 11'&$%Heap Implementation of Priority Queues• Store the entries of a priority queue in a heap.• Compare tree nodes/entries by their priorities.• The entry with the highest priority will always be the root ofthe tree.How do we enforce the first-come-first-serve discipline amongequal-priority entries ?CS 310 Heaps, Page 12'&$%Application 2: Heapsort21 3522 272345421945insert()remove()?HeapPhase-1. One by one, add all the data to a heap.Phase-2. One by one, remove all the entries from the heap.Who get out of the heap first ?Who is the second ?Who is the third ?CS 310 Heaps, Page 13'&$%A Tricky Implementation of HeapsortPhase-1: Insertions213522 27234542194521 3522 272345421945add 35swap 35and 21213522 2723454219452135352121 3522 27234542194521add 21CS 310 Heaps, Page 14'&$%2127213522 2723454219453521add 2222213522 27234542194535212227add 273522234542194535212227swap 27and 21CS 310 Heaps, Page 15'&$%21273522234542194535212227add 2323212735222345421945add 45 3522212723 45212735222345421945352221272345swap 45and 22CS 310 Heaps, Page 16'&$%212735222345421945352221272345swap 45and 35212735222345421945352221272345add 424221273522234542194535222127234542swap 42and 35CS 310 Heaps, Page 17'&$%212735222345421945add 1935222127234542192127352223454219453522212723454219 4add 421273522234542194 53522212723454219 4 5add 5CS 310 Heaps, Page 18'&$%21273522234542194535222127234219 45delete 4521273522234542194535222127234219 45swap 5and 4221273522234542194535222127234219 4swap 5and 355Phase−2: DeletionsCS 310 Heaps, Page 19'&$%21273522234542194 53522212723194521273522234542194 535222127231945swap 4and 3521273522234542194535222127231945swap 4and 22delete 42CS 310 Heaps, Page 20'&$%21273522234542194 522212723194 5remove 3521273522234542194 522212723194 5swap 19and 2721273522234542194 52221272319 4 5swap 19and 23CS 310 Heaps, Page 21'&$%21 273522234542194522212319 45remove 2721 273522234542194522212319 45swap 5and 2321 273522234542194522212319 45swap 5and 21CS 310 Heaps, Page 22'&$%21 273522234542194 522211945remove 2321 273522234542194 522211945swap 4and 22CS 310 Heaps, Page 23'&$%21 273522234542194 5211945remove 2221 273522234542194 52119 45swap 19and 2121 273522234542194519 45remove 2121 27352223454219451945swap 5and 19CS 310 Heaps, Page 24'&$%21 273522234542194 545remove 1921 273522234542194545swap 4and 521 273522234542194 54remove 521 273522234542194 5remove 4Array sortedCS 310 Heaps, Page 25'&$%Implementationvoid heapsort (int data[], int N){// Phase-1, N heap insertionsfor (int i=0; i<N; i++){// i is the index of the last entry in the heapint j;for (j=i; j>0 && data[j]>data[(j-1)/2]; j=(j-1)/2)swap (data[j], data[(j-1)/2]);}CS 310 Heaps, Page 26'&$%// Phase-2, N heap deletionsfor (int i=N; i>0; i--) {swap (data[0], data[i-1]);// Now the heap has only i-1 elementsint j=0;while ((2*j+1) < i-1) {int max_child = 2*j+1;if ((2*j+2)<i-1 && data[max_child]<data[2*j+2])max_child = 2*j+2;if (data[j] < data[max_child])swap(data[j], data[max_child]);elsebreak;j =