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