Design & Analysis of Algorithms
(MTCS102)
UNIT-1
Heap Sort Algorithm
From:
Asif Khan
Department of CSE
GNIOT, Greater Noida
Reference:
Thomas H. Corman et al.
The MIT Press
Heap
The binary heap is an array object that we can view as a
nearly complete binary tree. Each node of the tree
corresponds to an element of the array. The tree is
completely filled on all levels except possibly the last one,
which is filled from the left up to a point.
Heap
An array A that represents a heap is an object with two
attributes:
[Link], which (as usual) gives the number of elements
in the array, and
[Link]-size, which represents how many elements in the
heap are stored within array A.
That is, although A(1..[Link]) may contain numbers,
only the elements A(1..[Link]-size),
where 0 ≤ [Link]-size ≤ [Link], are valid elements of
the heap.
Heap
The root of the tree is A[1], and for a given index i of a
node, we can easily compute the indices of its parent, left
child, and right child:
Max-Heap and Min-Heap
There are two kinds of binary heaps: max-heaps and
min-heaps.
In both kinds, the values in the nodes satisfy a heap
property, the specifics of which depend on the kind of
heap.
In a max-heap, the max-heap property is that for every
node i other than the root,
A[PARENT(i)] ≥ A[i] ,
that is, the value of a node is at most the value of its
parent. Thus, the largest element in a max-heap is stored at
the root, and the subtree rooted at a node contains values
no larger than that contained at the node itself.
Heap Sort Algorithm
We will use following procedures in Heap Sort algorithm.
✓ The MAX-HEAPIFY procedure, which runs in O(lg n)
time, is the key to maintaining the max-heap property.
✓ The BUILD-MAX-HEAP procedure, which runs in
linear time, produces a maxheap from an unordered input
array.
✓ The HEAPSORT procedure, which runs in O(n lg n)
time, sorts an array in place.
MAX-HEAPIFY Algorithm
In order to maintain the max-heap property, we call the
procedure MAX-HEAPIFY.
Its inputs are an array A and an index i into the array.
When it is called, MAXHEAPIFY assumes that the binary
trees rooted at LEFT(i) and RIGHT(i) are maxheaps, but
that A[i] might be smaller than its children, thus violating
the max-heap property. MAX-HEAPIFY lets the value at
A[i] “float down” in the max-heap so that the subtree
rooted at index i obeys the max-heap property.
MAX-HEAPIFY Algorithm
MAX-HEAPIFY Algorithm
MAX-HEAPIFY Algorithm
Previous Figure shows the action of MAX-
HEAPIFY(A,2), where [Link]-size=10.
(a) is the initial configuration, with A[2] at node i=2
violating the max-heap property since it is not larger than
both children.
The max-heap property is restored for node 2 in (b) by
exchanging A[2] with A[4], which destroys the max-heap
property for node 4. The recursive call MAX-
HEAPIFY(A,4) now has i=4.
After swapping A[4] with A[9], as shown in (c), node 4 is
fixed up, and the recursive call MAX-HEAPIFY(A,9)
yields no further change to the data structure.
BUILD-MAX-HEAP Algorithm
Building a heap: We can use the procedure MAX-
HEAPIFY in a bottom-up manner to convert an array
A(1..n), where n=[Link], into a max-heap.
The elements in the subarray are all leaves
of the tree, and so each is a 1-element heap to begin with.
The procedure BUILD-MAX-HEAP goes through the
remaining nodes of the tree and runs MAX-HEAPIFY on
each one.
Building a Max-Heap
Building a Max-Heap
HEAPSORT Algorithm
The heapsort algorithm starts by using BUILD-MAX-
HEAP to build a max-heap on the input array A(1..n),
where n=[Link]. Since the maximum element of the
array is stored at the root A[1], we can put it into its
correct final position by exchanging it with A[n]. If we
now discard node n from the heap, by simply
decrementing [Link]-size, we observe that the children of
the root remain max-heaps, but the new root element
might violate the max-heap property. We can restore the
max-heap property, by calling MAX-HEAPIFY(A,1),
which leaves a max-heap in A(1..n). The heapsort
algorithm then repeats this process for the max-heap of
size n-1 down to a heap of size 2.
HEAPSORT Algorithm
Sorting of a Max-Heap
Sorting of a Max-Heap
Analysis of Heapsort Algorithm
The running time of MAX-HEAPIFY on a subtree of size
n rooted at a given node i is the θ(1) time to fix up the
relationships among the elements A[i] and its children,
plus the time to run MAX-HEAPIFY on a subtree rooted
at one of the children of node i.
The children’s subtrees each have size at most 2n/3. The
worst case occurs when the bottom level of the tree is
exactly half full, and therefore we can describe the
running time of MAX-HEAPIFY by the recurrence:
T(n) ≤ T(2n/3) + θ(1)
The solution to this recurrence, by case 2 of the master
theorem), is T(n) = O( lg n ).
Analysis of Heapsort Algorithm
The running time of BUILD-MAX-HEAP on a subtree of
size n rooted at a given node i is O(n lg n).
As build max heap call MAX-HEAPIFY n/2 times to
build the heap and the running time of MAX-HEAPIFY is
O(lg n), So T(n) = n/2 * O(lg n) = O(n lg n)
The HEAPSORT procedure will also takes time O(n lg n),
since the call to BUILD-MAXHEAP takes time O(n lg n)
and each of the n-1 calls to MAX-HEAPIFY takes time
O(lg n). So T(n) = O(n lg n) + (n-1) * O(lg n)
= O(n lg n)
THANK YOU