HEAPS AND HEAPSORT

 

HEAPS:

• The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree.
• Each node of the tree corresponds to an element of the array that stores the value in the node
• The tree is completely filled on all levels except possibly the lowest, which is filled from left up to a point.
• An array A that represent the heap is an object with two attributes:
• length[A], which is the number of elements in the array
• heap_size[A]: the number of elements in the heap stored within array A.
• The root of the tree is a[1]
• Given the index I of the node,
• PARENT(i)

                           Return 

• LEFT(i)

Return 2i

• RIGHT(i)

Return 2i + 1

                 A

• There are two kinds of binary heaps

1. Max-Heap
2. Min-Heap

MAX-HEAP PROPERTY:

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 the value no larger than that contained at the node itself.

MIN-HEAP PROPERTY:

 

A[PARENT(i)] ≤ A[i]

Here, the smallest element is stored at the root, and the subtree rooted at a node contains the value larger than that contained at the node itself.

• For the heapsort algorithm we use max-heap.
• Min heaps are used in priority queues.
• Viewing the heap as a tree, the height of the node is the number of edges on the longest simple downward path from the node to the leaf.

The height of the heap is same as height of its root.

Since the height of n elements is based on a complete binary tree, so its height is O(log n) time.

MAX-HEAPIFY PROCEDURE: Maintaining the heap property

 

Input: Array A and an index l into the array,

• When MAX-HEAPIFY is called, it is assumed that the binary tree rooted at LEFT(i) AND RIGHT(i) are max-heap; but that A[i] may be smaller than its children, thus violating the max-heap property.
• The function of MAX-HEAPIFY is to let the value at A[i] “float down” in the max-heap so that the subtree rooted at index i becomes a max-heap.

MAX-HEAPIFY (A, i)

1. l ← LEFT (i)
2. r ← RIGHT (i)
3. if l ≤ heap_size [ A ] and A [l ] > A[ i ]
4.             largest ← l
5. else largest ← i
6. if r ≤ heap_size [ A ] and A[ r ] > A[ largest]
7.            largest ← r
8. if largest ≠ i
9.            Exchange  A[ i ] ↔ A[ largest ]
10.            MAX-HEAPIFY ( A, largest )

• At each step, the largest of the elements A[ i ], A[ LEFT(i) ] AND A[ RIGHT(i) ] is determined and it’s index is stored in a variable called largest.
• If A[ i ] is the largest, then the subtree rooted at node i is a max-heap and the procedure terminates.
• Otherwise one of the two children has the largest element, and A[ i ] is swapped with A[ largest ], which causes node i and its children to satisfy the max-heap property.
• The node indexed by largest, however now has the original value A[ i ], and thus the subtree rooted at largest may violate the max-heap property.
• MAX-HEAPIFY must be called recursively on that subtree.
• The running time of the MAX-HEAPIFY on a node of height h is O( h )

i.e.  T( n ) = O( log n )

Example:

MAX-HEAPIFY (A, 2)

Where, heap_size [ A ] = 10

The largest is A[ 4 ]. Hence, exchanging A[ 2 ] ↔ A[ 4 ].

Recursive call – MAX-HEAPIFY ( A, 4 )

The largest is A[ 9 ]. Hence, exchanging  A[ 4 ] ↔ A[ 9 ].

 

BUILD-MAX-HEAP:

 

• Procedure produces a max-heap from an unordered input array.
• We can use the procedure MAX-HEAPIFY in a bottom-up manner to convert an array A [ 1,…….. n ] into a max-heap (where n = length of array A).
• The elements in the sub array A [ (+ 1 )……. n ] are all leaves of tree, so each is a 1-element heap to begin with.

BUILD-MAX-HEAP ( A )

1. heap_size [ A ] ← length [A ]
2. for i ← down to 1
3. do  MAX-HEAPIFY (A, i )

Example:

BUILD-MAX-HEAP begins when

i ←⌊10/2⌋

i ← 5

Next iteration is,  i ← 4

At node 4 MAX-HEAPIFY will ensure correct position for node 4 i.e. value 2 and the value 14 will be swapped.

Next iteration is, i ← 3

At node 3 MAX-HEAPIFY will ensure correct position for node 3 i.e. value 3 and the value 10 will be swapped

Next iteration is, i ← 2

At node 2 MAX-HEAPIFY will ensure correct position for node 2 i.e. value 1 and the value 16 will be swapped and again MAX-HEAPIFY will be recursively applied at all nodes and at node 5 the value 1 will be swapped and at node 10 value 7 will be swapped.

Next iteration is i ← 1

After the iteration i = 1 i.e. applying MAX-HEAPIFY recursively on all nodes, the final heap will appear as seen below,

The upper bound on the running time of BUILD-MAX-HEAP is as follows.

• Each call to MAX-HEAPIFY costs O ( log n ) time, and BUILD-MAX-HEAP makes O(n) such calls. Thus the running time is O ( nlog n ). This upper bound is not asymptotically tight.
• To find tighter bound by observing the time taken for MAX-HEAPIFY to run a node varies with the height of the node in the tree and the height of most nodes are small, and the tighter analysis relies on the properties that the n elements heap has height  and   most nodes of any height h. So the equation becomes

THE 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 = length [ A ].
• Since the maximum elements of the array is sorted at the root A[ 1 ], it can be put into its correct final position by exchanging it with A [ n ].
• If we now “discard” node n from the heap (by decreasing the heap_size), we observe that A [ 1…….(n-1) ] it can easily be made into max-heap.
• The children of the root remain as max-heaps, but the new root element may violate the max-heap property.
• All that is needed to restore the max-heap property, is just one call to 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_size 2.

HEAPSORT ( A )

1. BUILD-MAX-HEAP ( A )
2. for i ← length[ A ] down to 2
3.          do exchange  A[ 1 ] ↔ A[ i ]
4. heap_size [ A ] ← heap_size [ A ]-1
5.           MAX-HEAPIFY ( A,1 )

COMPLEXITY:

The HEAPSORT procedure takes time O(n log n ), since the call to BUILD-MAX-HEAP takes time O( n ) and each of ( n-1 ) calls to MAX-HEAPIFY takes time O( log n ).

Eg:

(A)                                                                                  (B)

                                  

(C)                                                     (D)

(E)                                                   (F)

(G)                                        (H)                                                (I)

                                 

(J)

                             

The operation of HEAPSORT(A) builds the max-heap data structure just after BUILD-MAX-HEAP in line 1. In figures (B) to (J), the max heap just after each call of MAX-HEAPIFY in line 5, shows the value of i at that time. The array contains the elements which are sorted in non-decreasing order.

Author: TILAK SHANTARAM NAYAK

USN: 1CR15IS110