Heap Sort Algorithm

5 min readSep 27, 2022

A in-place sorting algorithm that sorts an unordered array by virtually dividing the array into sorted and unsorted subarrays. It maintains the unsorted part in a heap data structure. The minimum/maximum element at the root in the heap is extracted and inserted to the sorted subarray in each step until the heap was left with only one element. Heap sort algorithm is efficient and runs in O(nlog(n)) time.

Table of Contents· Array Representation of Binary Heap
· How Does Heap Sort Algorithm work?
  ∘ Heapify(Sift Down)
· Graphical Explanation
  ∘ step1: build a max heap
  ∘ step2: swap the root with the last element in the heap
  ∘ step3: reduce heap size by 1
  ∘ step4: heapify the root
  ∘ step5: Repeat step 2, step 3 and step 4 until the array is completely sorted
· Code Implementation
  ∘ Complexity
  ∘ Pseudocode
  ∘ Golang
  ∘ Python

Before we dive into heap sort algorithm, you can check Golang: Heap data structure to get more details about heap data structure.

Array Representation of Binary Heap

Heap can be represented in form of array.

If the index of an element in the array is i, the left and right child of the element are at the index 2*i+1 and 2*i+2 respectively. The index of the element’s parent is the lower bound of (i-1)/2. Root is always at the index 0 and the index of last non-leaf node can be calculated by (array length — 2)/2.

current element: i
parent: (i-1)/2 (round down)
left child: 2*i + 1
right child: 2*i + 2
root: 0
the last non-leaf node: (array length-2)/2 (round down)

How Does Heap Sort Algorithm work?

Heap sort splits the input array into two subarrays, unsorted subarray on the left and sorted one on the right. At the beginning, the unsorted subarray contains the entire array and sorted subarray is empty.

First, it transforms the unsorted subarray into a heap data structure. Build a max/min heap if the array is supposed to be sorted in ascending/descending order. That way, it is easy to get the maximum/minimum value at the root.

Secondly, swap the root with the last element in the heap. After swapping, the original root element is placed at the correct position in the sorted output.

However, the heap is not satisfy the heap property anymore because of the new root. We need to re-heapify the root.

Repeat the process of swap and heapify the root, we can build the sorted output from the back.

Heapify(Sift Down)

Heapify is a process of converting a binary tree to a heap data structure.
1. Compare the the value of a node with the value of its child nodes
2. If the node’s value is smaller/larger than the largest/smallest child node, swap the node and the largest/smallest child node for constructing the max/min heap.
3. repeat step 1 and step 2 until the heap property is satisfied.

Graphical Explanation

step1: build a max heap

transform the unsorted subarray into a max heap

heapify all the non-leaf nodes in the bottom-up orderheapify: 
1. find the largest child node
2. compare current node with the largest child node
   - current node < the largest child node ➞ swap ➞ go to 1.
   - current node > the largest child node ➞ stop ➞ visit next non leaf node

step2: swap the root with the last element in the heap

step3: reduce heap size by 1

shrink the heap/unsorted subarray.

step4: heapify the root

After swapping the root with the last element in step 2, the heap doesn’t satisfy max-heap property. We need to heapify the root node to allow the maximum value at the root.

step5: Repeat step 2, step 3 and step 4 until the array is completely sorted

Code Implementation

Complexity

Time: O(nlog(n))
Space: O(1)
n: the total number of elements in the array

Pseudocode

heap sort

array: input array
endIdx: array length - 1# build a max heap
max-heap = buildMaxHeap(array)for endIdx from endIdx to 1:
    # swap the root and the last element in the heap
    max-heap[0], max-heap[last] = max-heap[last], max-heap[0]    # reduce the size of heap by 1
    # heapify the heap
    heapify(0, endIdx - 1, array)

build a max heap

lastNonLeafNodeIdx = (array length - 2) / 2
endIdx = array length - 1for currentIdx from lastNonLeftNodeIdx to 0:
    heapify(currentIdx, endIdx, array)

heapify(sift down)

i: current index
endIdx: array length - 1leftChildIdx = 2 * i + 1
rightChildIdx = 2 * i + 2
while childOneIdx <= endIdx:
    largestChildIdx = leftChildIdx
    if array[leftChildIdx] < array[rightChildIdx):
        largestChildIdx = rightChildIdx
 
    if array[i] < array[largestChildIdx]:
        swap array[i] and array[largestChildIdx]
        i = largestChildIdx
        leftChildIdx = 2 * i + 1
    else:
        return

Golang

Python

You can access the source code here.

Golang: Heap data structure

Other sorting algorithms: