Heap Building and Heap Sort

Heap is a very useful data structure that every programmer should know well. The heap data structure is used in Heap Sort, Priority Queues. The understanding of heaps helps us to know about memory management. In this blog, we will discuss the various about Heap Building and Heap Sort. So Let’s get started.

We have already discussed what are heaps, its structure, types, and its representation in the array and operations on heaps.

Heap Building

To build a max-heap, we can use down_heapify() method to make a max-heap or a min-heap property out of an array. (Think!)

The idea is to heapify the complete binary tree formed from the array in reverse level order following the top-down approach.

We can eliminate the operations for the leaf nodes as they follow the heap property. Also, the array representation of the complete binary tree contains the level order traversal of the tree.

So the idea is to find the position of the last non-leaf node and perform the down_heapify() operation of each non-leaf node in reverse level order.

Example

For, the given array Arr[] = { 2, 5, 4, 8, 9, 10, 11}

Pseudo-Code

void build_heap (int Arr[ ])
{
   for(int i = N/2-1 ; i >= 0; i-- )
   {
      down_heapify (Arr, i, N);
   }
}

Time Complexity

The complexity of the build_heap is O(N). down_heapify() function has complexity logN and the build_heap functions run only N/2 times, but the amortized complexity for this function is actually linear i.e. O(N)
For more details, you can refer to this.

Heap Sort

Heaps can also be used in sorting an array. In the case of max-heaps, the maximum element is always present at the root of the heap. So we can use this property of the heap to sort an array.

The idea is to pop out the maximum element i.e. root of the heap and then again heapify the array such that 2nd maximum element will be at the root of the heap. This process will continue until we pop out each element from the heap.

Consider an array that is to be sorted using heap sort. The steps we follow during heap sort are:-

• Initially build a max heap of elements in Arr.
• The root element contains the maximum element i.e. Arr[0]. So swap that element will last element of the heap and then heapify the heap excluding the last element. The last element has got the correct position in the sorted array, so we will decrease the size of the heap by one.
• Repeat the last step, till the size of the heap becomes zero or all elements are in their correct position.

Illustration

For, the max-heap Arr[] = { 11, 9, 10, 8, 5, 2, 4}

Pseudo-Code

void heap_sort(int Arr[], int N)
{
    build_heap(Arr);
    
    for(int i = N-1; i >= 1; i--)
    {
        swap(Arr[i], Arr[0]);
        down_heapify(Arr, 0, i+1);
    }
}

→ For the implementation of down_heapify() refer to the blog operation of heaps.

Time Complexity

The complexity of the heap sort is O(NlogN) as we run the down_heapify() operations N-1 times and the complexity of down_heapify() is O(logN) and the complexity of the building the heap is O(N).

T(Heap Sort) = T(build Heap) + (N-1)*T(down_heapify)
             = O(N) + (N-1)*O(logN)
             = O(N) + O(NlogN)
             = O(NlogN)

Suggested Problems to solve

• Find kth largest element in an array
• Top k Frequent Elements
• K Pairs with Smallest Sums
• Sliding window maximum
• Merge K sorted list
• Convert a min-heap to max heap

Happy coding! Enjoy Algorithms.