Friday, Jul 20th

Last update12:59:40 PM GMT

Heap and Heap Sort

Write e-mail

A heap is a binary tree based data structure, which is basically stored in form of an array instead of linked lists, and for element at index i(except the root element), key[i] < key[parent(i)] where parent(i) represents the index of the parent element in the tree. This is also known as max heap. The root of the tree is A[1], and given the index i of a node, the indices of its parent PARENT(i), left child LEFT(i), and right child RIGHT(i) can be computed as:

argaiv1697

  • PARENT(i) : return floor(i/2), where floor(n) is greatest integer less than n
  • left (i) : return 2i
  • right (i) : return 2i + 1

A min heap is a data structure opposite to the max heap. That is, for the element at the position i(except the root element), key[i] > key[parent(i)].

Before we proceed to Heap Sort, we need to understand few of the basic heap routines.

Max Heapify

It’s a routine to maintain a heap as max heap after insertion of a new element at the index i, when the assumption is that rest of the tree is max heap. The algorithm, MAX-HEAPIFY(A, i), for the array A works the following way:

MAX-HEAPIFY(A, i) {
l = left(i)
r = right(i)
if l ≤ heap-size[A] and A[l] > A[i] 
    then largest =l
else
    largest=i
if r ≤ heap-size[A] and A[r] > A[largest]
    then largest =r
if largest != i
    then exchange A[i ] and A[largest]
MAX-HEAPIFY(A, largest)
}

Creating a Max heap from an unsorted array

If we max heapify, starting from the lowest level parent element, we will have the max heap. So, we need to max heapify elements from the index floor(n/2) down to 1, where n is the length of array A. The algorithm for the same is

BUILD-MAX-HEAP(A) {
heap-size[A] = length[A]
for i = floor(length[A]/2) downto 1
    do MAX-HEAPIFY(A, i)
}

Heap Sort

Now if we have a max heap, we are sure that the root element of this tree is the largest number. And now we exchange the last and the first element, placing the largest number at the last index of the array. Now, we have the largest number at the end of the array. But, now the array is not max heap. Let us decrease the size of the heap, by ignoring the last index of the array. That is, the heap is of size N-1, and if we apply MAX-HEAPIFY method on the index 1, we get a max heap of size N-1. And again, if we exchange the elements at index 1 and N-1, we have the second largest number at second last position in the array. And this way, we keep on repeating the process till the heap size of 2.

HEAPSORT(A) {
BUILD-MAX-HEAP(A)
for i = length[A] downto 2
    do exchange A[1] and A[i]
heap-size[A] = heap-size[A] − 1
MAX-HEAPIFY(A, 1)
}

Share this post



Add comment

Please refrain from using slang or abusive language in the comments.
To avoid waiting for your comment to be published after being reviewed, please log in as a registered user.


Security code
Refresh

Web Hosting