Pseudo Code

Lesson 4 of 9 in Coddy's Heap Sort - DSA Series course.

siftDown(array, i, size):
   loop:
      largest = i
      left = 2*i + 1
      right = 2*i + 2
      if left < size and array[left] > array[largest]:  largest = left
      if right < size and array[right] > array[largest]: largest = right
      if largest == i: stop
      swap array[i] and array[largest]
      i = largest

heapSort(array):
   n = length(array)
   for i from n/2 - 1 down to 0:   # build max-heap
      siftDown(array, i, n)
   for end from n-1 down to 1:     # extract max repeatedly
      swap array[0] and array[end]
      siftDown(array, 0, end)

siftDown pushes a too-small parent down past its larger child until the max-heap property is restored. size is how much of the array is still part of the heap.
Build phase: sifting down every non-leaf node (from the last parent, index n/2 - 1, up to the root) turns any array into a max-heap.
Sort phase: each step moves the current maximum to the end and shrinks the heap, so the array fills up sorted from the back.

Try it yourself

This lesson doesn't include a code challenge.