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:

- PARENT
*(i) :***return**floor(*i/*2), where floor(n) is greatest integer less than n - left
*(i) :***return**2*i* - right
*(i) :***return**2*i*+ 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:

**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

**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.

< Previous | Next > |
---|

To avoid waiting for your comment to be published after being reviewed, please log in as a registered user.