Menu

DAA ASSIGNMENT

February 22, 2019 0 Comment

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