Skip to content

Heapsort

This page gives a brief introduction to heapsort.

Definition

Heapsort is a sorting algorithm designed around the binary heap data structure. It operates on arrays.

Procedure

Heapsort is essentially selection sort built on a heap.

Sorting

First build a max-heap. Then take the element at the top of the heap, which is the maximum, swap it with the element at the end of the array, and restore the heap property of the remaining heap.

Next, take the element at the top of the heap, which is the second largest, swap it with the second-to-last element of the array, and restore the heap property of the remaining heap.

Continue in the same way: after operation number \(n-1\), the whole array is sorted.

Building a binary heap on an array

Starting from the root, lay the nodes out in the array one level after another.

The parent, left child and right child of the node at index i of the array are then:

1
2
3
iParent(i) = (i - 1) / 2;
iLeftChild(i) = 2 * i + 1;
iRightChild(i) = 2 * i + 2;

Properties

Stability

As in selection sort, the swaps in heapsort can change the relative order of equal elements, so it is an unstable sorting algorithm.

Time complexity

The worst-case time complexity of heapsort is \(O(n\log n)\).

Space complexity

The heap can be built on the input array itself, so heapsort is an in-place algorithm.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void sift_down(int arr[], int start, int end) {
  // compute the indices of the parent and the child
  int parent = start;
  int child = parent * 2 + 1;
  while (child <= end) {  // compare only while the child index is in range
    // first compare the two children and pick the larger one
    if (child + 1 <= end && arr[child] < arr[child + 1]) child++;
    // if the parent is larger than the child, the adjustment is done: return at once
    if (arr[parent] >= arr[child])
      return;
    else {  // otherwise swap parent and child, then compare the child with the grandchild
      swap(arr[parent], arr[child]);
      parent = child;
      child = parent * 2 + 1;
    }
  }
}

void heap_sort(int arr[], int len) {
  // sift down from the parent of the last node backwards to heapify the array
  for (int i = (len - 1 - 1) / 2; i >= 0; i--) sift_down(arr, i, len - 1);
  // swap the first element with the one just before the already sorted elements, then readjust (the elements before the one just placed); repeat until sorted
  for (int i = len - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    sift_down(arr, 0, i - 1);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def sift_down(arr, start, end):
    # compute the indices of the parent and the child
    parent = int(start)
    child = int(parent * 2 + 1)
    while child <= end:  # compare only while the child index is in range
        # first compare the two children and pick the larger one
        if child + 1 <= end and arr[child] < arr[child + 1]:
            child += 1
        # if the parent is larger than the child, the adjustment is done: return at once
        if arr[parent] >= arr[child]:
            return
        else:  # otherwise swap parent and child, then compare the child with the grandchild
            arr[parent], arr[child] = arr[child], arr[parent]
            parent = child
            child = int(parent * 2 + 1)


def heap_sort(arr, len):
    # sift down from the parent of the last node backwards to heapify the array
    i = (len - 2) // 2
    while i >= 0:
        sift_down(arr, i, len - 1)
        i -= 1
    # swap the first element with the one just before the already sorted elements, then readjust (the elements before the one just placed); repeat until sorted
    i = len - 1
    while i > 0:
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(arr, 0, i - 1)
        i -= 1