Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Motivation

Mergesort has a good worst case of but needs extra arrays for merging. Heapsort has the same worst case and sorts in place.

Idea

Steps on A[1..n]:

  • step 1: heapify A into a maxheap, so the maximum is at A[1]
  • step 2: exchange A[1] with A[n], which puts the maximum in its final place at the end
  • step 3: treat A[1..n-1] as the new heap and siftdown from the root, which is the same as deleting the root
  • repeat steps 2 and 3 with

Example

Start with A = [3, 6, 10, 18, 8, 7, 25, 40]. Heapify gives [40, 18, 25, 6, 8, 7, 10, 3].

Swap with the last value , so is fixed at index 8. Siftdown on the first 7 cells gives [25, 18, 10, 6, 8, 7, 3 | 40]. The next round fixes at index 7, and so on.

Code

def heapsort(A):                   # A[1..n], A[0] unused
    heapify(A)
    for last in range(len(A) - 1, 1, -1):
        A[1], A[last] = A[last], A[1]      # max goes to the end
        siftdown_range(A, 1, last - 1)     # heap is now A[1..last-1]
 
def heapify(A):
    n = len(A) - 1
    for i in range(n // 2, 0, -1):         # from index n/2 down to 1
        siftdown_range(A, i, n)
 
def siftdown_range(A, i, n):
    largest = i
    l, r = 2 * i, 2 * i + 1
    if l <= n and A[l] > A[largest]:
        largest = l
    if r <= n and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        siftdown_range(A, largest, n)

Complexity

Heapify costs and each of the siftdowns costs :

AlgorithmWorst caseAverage case
Mergesort
Heapsort
Quicksort