Page 263 - DCAP407_DATA_STRUCTURE

Data Structure

sorting algorithm which has a worst-case O(n log n) runtime. This is a two-stage algorithm which is as
follows:
Stage 1: (Heap construction): Construct a heap for a given array.

Stage 2: (Maximum deletions): Apply the root-deletion operation n−1 times to the remaining heap.
The pseudo code for the algorithm is shown below.
Heapify(A, n){ // heapify converts initial array into heap
l <- left(n)
r <- right(n)
if l <= heapsize[A] and A[l] > A[n] // the root is compared with its two children

then largest <- l
else if largest <- n
if r <= heapsize[A] and A[r] > A[largest]
then largest <- r
if largest != n
then swap A[n] <-> A[largest] // the larger child is swapped with the root
Heapify(A, largest) // heapify algorithm is applied to the larger node
}

Buildheap(A){
heapsize[A] <- length[A]
for n<- |length[A]/2| down to 1
do Heapify(A, n)
}
Heapsort(A){

Buildheap(A)
for n<- length[A] downto 2
do swap A[1] <-> A[n]
heapsize[A] <- heapsize[A] - 1
Heapify(A, 1)
}
Heap sort first converts the initial array into a heap. The heapsort algorithm uses ‘heapify’ method to
complete the task. The heapify algorithm, as given in the above code, receives a binary tree as input and
converts it to a heap. Then, the root is compared with its two children, and the larger child is swapped
with it. This may result in one of the left or right sub-trees losing the heap property. As a result, the
heapify algorithm is recursively applied to the suitable sub-tree rooted at the node whose value was
swapped with the root. This process continues until a leaf node is reached, or until the heap property is
satisfied in the sub-tree.

256 LOVELY PROFESSIONAL UNIVERSITY