Heap Sort

What is heap sort?

Heap sort is based exclusively upon a binary heap data structure, where we find the largest element and sort it to the end of our unsorted collection. We use the properties of a complete binary tree to sort our collection efficiently.

Time and Space Complexities:

• Best Time Complexity: O(n log(n))
• Average Time Complexity: O(n log(n))
• Worst Time Complexity: O(n log(n))
• Best Space Complexity: O(1)

Prerequisites:

• Recursion
• Binary Heap

Steps to perform heap sort:

1. We start by using Heapify to build a max heap of elements present in an array A.
2. Once the heap is ready, the largest element will be present in the root node of the heap that is A[1].
3. Now swap the element at A[1] with the last element of the array, and heapify the max heap excluding the last element.
4. Repeat steps 2 and 3 till all the elements in the array are sorted.

Pseudocode:

Heapify(A as array, n as int, i as int)
{
    max = i
    leftchild = 2i + 1
    rightchild = 2i + 2

    if (leftchild <= n) and (A[i] < A[leftchild])
        max = leftchild
    else 
        max = i

    if (rightchild <= n) and (A[max]  > A[rightchild])
        max = rightchild

    if (max != i)
        swap(A[i], A[max])
        Heapify(A, n, max)
}

Heapsort(A as array) 
{
   n = length(A)
   for i = n/2 downto 1   
     Heapify(A, n ,i)
   
   for i = n downto 2
     exchange A[1] with A[i]
     A.heapsize = A.heapsize - 1
     Heapify(A, i, 0)
}

Let’s Code

To code in any language other than Python, 👉 Click here 👈