Heap Sort

Heap Sort Definition

HeapSort is a comparison based sorting technique where we first build Max Heap and then swaps the root element with last element (size times) and maintains the heap property each time to finally make it sorted.

Heapsort is a comparison-based sorting algorithm that uses a binary heap data structure. Like mergesort, heapsort has a running time of O(n\log n),O(nlogn), and like insertion sort, heapsort sorts in-place, so no extra space is needed during the sort.

The binary heap data structure allows the heapsort algorithm to take advantage of the heap's heap properties and the heapsort algorithm makes use of the efficient running time for inserting to and deleting from the heap.

What Is Heap Sort?

To understand how heap sort works, we first need to understand some basic concepts related to binary heaps. Feel free to skip them if you are already familiar with these concepts.

Binary Heap

Heap is a tree-based data structure in which all the tree nodes are in a particular order, such that the tree satisfies the heap properties (that is, there is a specific parent-child relationship that is followed throughout the tree).

A heap data structure where the tree is a complete binary tree is referred to as a binary heap.

Heap Sort Definition

Heap sort is an efficient comparison-based sorting algorithm that creates a heap from the input array and then sorts the array by taking advantage of a heap's properties.

Please keep in mind, since the heap is a tree-based data structure, this also means that the knowledge of arrays, trees, binary trees, and heaps is key to understanding the heap sort algorithm.

What is meant by Heapify?

Heapify is the process of creating a heap data structure from a binary tree represented using an array. It is used to create Min-Heap or Max-heap. Start from the first index of the non-leaf node whose index is given by n/2 – 1. Heapify uses recursion

Algorithm for Heapify:

heapify(array) Root = array[0]

Largest = largest( array[0] , array [2 * 0 + 1]/ array[2 * 0 + 2]) if(Root != Largest) Swap(Root, Largest)

How does Heapify work?

Array = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17} Corresponding Complete Binary Tree is:

             1
          /     \
       3         5
    /    \     /  \
  4      6   13  10
 / \    / \

9 8 15 17

The task to build a Max-Heap from above array.

Total Nodes = 11. Last Non-leaf node index = (11/2) – 1 = 4. Therefore, last non-leaf node = 6.

To build the heap, heapify only the nodes: [1, 3, 5, 4, 6] in reverse order.

Heapify 6: Swap 6 and 17.

             1
          /     \
       3         5
    /    \      /  \
 4      17   13  10
/ \    /  \

9 8 15 6

Heapify 4: Swap 4 and 9.

             1
          /     \
       3         5
    /    \      /  \
 9      17   13  10
/ \    /  \

4 8 15 6

Heapify 5: Swap 13 and 5.

             1
          /     \
       3         13
    /    \      /  \
 9      17   5   10
/ \    /  \

4 8 15 6

Heapify 3: First Swap 3 and 17, again swap 3 and 15.

            1
        /      \
     17         13
   /    \      /  \
 9      15   5   10
/ \    /  \

4 8 3 6

Heapify 1: First Swap 1 and 17, again swap 1 and 15, finally swap 1 and 6.

             17
          /      \
      15         13
     /    \      /  \
    9      6    5   10
   / \    /  \
  4   8  3    1

Heap Sort Algorithm

First convert the array into heap data structure using heapify, than one by one delete the root node of the Max-heap and replace it with the last node in the heap and then heapify the root of the heap. Repeat this process until size of heap is greater than 1.

Follow the given steps to solve the problem:

Build a max heap from the input data. At this point, the maximum element is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of the heap by 1. Finally, heapify the root of the tree. Repeat step 2 while the size of the heap is greater than 1.

Note: The heapify procedure can only be applied to a node if its children nodes are heapified. So the heapification must be performed in the bottom-up order.

Detailed Working of Heap Sort

To understand heap sort more clearly, let’s take an unsorted array and try to sort it using heap sort. Consider the array: arr[] = {4, 10, 3, 5, 1}.

Build Complete Binary Tree: Build a complete binary tree from the array.

Transform into max heap: After that, the task is to construct a tree from that unsorted array and try to convert it into max heap.

• To transform a heap into a max-heap, the parent node should always be greater than or equal to the child nodes
• Here, in this example, as the parent node 4 is smaller than the child node 10, thus, swap them to build a max-heap.

Transform it into a max heap image widget

• Now, as seen, 4 as a parent is smaller than the child 5, thus swap both of these again and the resulted heap and array should be like this:

Perform heap sort: Remove the maximum element in each step (i.e., move it to the end position and remove that) and then consider the remaining elements and transform it into a max heap.

• Delete the root element (10) from the max heap. In order to delete this node, try to swap it with the last node, i.e. (1). After removing the root element, again heapify it to convert it into max heap.
• Resulted heap and array should look like this:

• Repeat the above steps and it will look like the following:

Now remove the root (i.e. 3) again and perform heapify.

• Now when the root is removed once again it is sorted. and the sorted array will be like arr[] = {1, 3, 4, 5, 10}.

Implementation of Heap Sort

Below is the implementation of the above approach:

Heap Sort - Python Implementation

Output

Sorted array is 5 6 7 11 12 13

Time Complexity: O(N log N) Auxiliary Space: O(1)

Some FAQs related to Heap Sort

What are the two phases of Heap Sort?

The heap sort algorithm consists of two phases. In the first phase the array is converted into a max heap. And in the second phase the highest element is removed (i.e., the one at the tree root) and the remaining elements are used to create a new max heap.

Why Heap Sort is not stable?

Heap sort algorithm is not a stable algorithm. This algorithm is not stable because the operations that are performed in a heap can change the relative ordering of the equivalent keys.

Is Heap Sort an example of “Divide and Conquer” algorithm?

Heap sort is NOT at all a Divide and Conquer algorithm. It uses a heap data structure to efficiently sort its element and not a “divide and conquer approach” to sort the elements.

Which sorting algorithm is better – Heap sort or Merge Sort?

The answer lies in the comparison of their time complexity and space requirement. The Merge sort is slightly faster than the Heap sort. But on the other hand merge sort takes extra memeory. Depending on the requirement, one should choose which one to use.

Why Heap sort better than Selection sort?

Heap sort is similar to selection sort, but with a better way to get the maximum element. It takes advantage of the heap data structure to get the maximum element in constant time.