DAA ASSIGNMENT (TOPIC: HEAP SORT) HEAPS It is a specially balanced binary tree data structure. The root node of the heap is compared with its children and are arranged accordingly. A B (PARENT NODE) (CHILD NODE) PROPERTY: MIN HEAP PROPERTY In this case the value of the root node is less than or equal to the child node.
MAX HEAP PROPERTY In this case the value of the root node is greater than or equal to the child node. 9 75 4 68 Maintaining the heap property:- Heapifyisthemethodusedinordertomanipulatetheheapstructures. “HEAPIFY”islettingthevalueatAigoingdownintheheapsothatthesubtreerootedwithindexIbecomesaheap. PSEUDOCODE: MAX-HEAPIFY(A,i) {l=2i; r=2i+1; if(lai) largest=l; else largest=i; if(ralargest) largest=r; If(largest!=i) ExchangeAiwithAlargest MAX-HEAPIFY(A,largest)} HEAP BUILDING:- PSEUDOCODE: BUILD-MAX-HEAP( A ) { A.heap_size=A.length; for ( i= (A.length/ 2 )down to 1 ) MAX-HEAPIFY( A , i) } NOTE : The running time of ‘Build heap’ is O(n).
PRIORITY QUEUE: ?Aheapisusefuldatastructurewhenwewanttoremovetheelementonthebasisofpriority. ?Acommonuseofheapsistoimplementthepriorityqueue. ?Priorityqueueareusedinsituationsorapplicationswhichinvolvestheuseofpriorityasapropertytoprocesstheelements. ?Themajoroperationsareinsertionanddeletion.Theelementwithhighestpriorityissetatfrontandlowestatend.Hence, itispossible,ifweenqueueanelementhavinghigherpriority,itcanmovetofrontofthequeue. ?ItwilltakeO(logN)timetoinsertanddeleteeachelementinthepriorityqueueusingheaps. HEAP SORT ALGORITHM: Combining the best of both the insertion and merge sort, the heap sort algorithm starts by using the procedure MAX-BUILD- HEAP to build a ( max ) heap on an input array.
After this using a loop we exchange the first element with the last one reducing the size of the heap till index 2.At the end MAX-HEAPIFY function is called . PSEUDOCODE: HEAP-SORT(A) {BUILD-MAX-HEAP (A) For i= length A down to 2 do exchange A1 with Ai heap_sizeA =heap_sizeA –1 MAX-HEAPIFY (A , 1 ) } BEGIN HEAPIFY(array) Len = array.length; i=len-1; Root =0; i> rooti– ENDTemp=arrayi; Arrayi=arrayroot; Arrayroot=temp; Length –; Shiftdown(array,root,length–1) FLOW CHART: THANK YOU SUBMITTED BY: PALAK MANGAL 16BCS032
