Unfortunately heapsort is not stable so sorting a list that is already sorted could quite possibly end up in a different order.

Complexity

Time			Space
Worst case	Best case	Average case	Worst case
O(n \log n)	O(n \log n)	O(n \log n)	O(1) auxiliary

In-place

The heap can be represented by an array as described in the binary heap article.

Construction of the heap can be done in place on the array. I mentioned earlier that when we use a min-heap they come out in ascending order, and a max-heap for descending. When performing an in-place sort we want to reverse this as we will be constructing the sorted list backwards. First, the heap is constructed in place, then we swap the root of the heap (index = 0) with the last element of the heap (index = max), the heap’s size is reduced by one and it repeats until there is only 1 element left in the heap which will be in the correct position.

Visualisation

Use the controls to playback heapsort on the data set.

See the Sorting Visualiser page for more visualisations.

Code

Here is a heapsort implementation done in Java using a max-heap.

public class Heapsort<T> : IGenericSortingAlgorithm<T> where T : IComparable
{
    public void Sort(IList<T> list)
    {
        int heapSize = list.Count;
        BuildHeap(list, heapSize);
        while (heapSize > 1) {
            Swap(list, 0, heapSize - 1);
            heapSize--;
            Heapify(list, heapSize, 0);
        }
    }

    private void BuildHeap(IList<T> list, int heapSize) {
        for (int i = (int)(list.Count / 2); i >= 0; i--) {
            Heapify(list, heapSize, i);
        }
    }

    private void Heapify(IList<T> list, int heapSize, int i) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int largest;
        if (left < heapSize && list[left].CompareTo(list[i]) > 0)
            largest = left;
        else
            largest = i;
        if (right < heapSize && list[right].CompareTo(list[largest]) > 0)
            largest = right;
        if (largest != i) {
            Swap(list, i, largest);
            Heapify(list, heapSize, largest);
        }
    }

    private void Swap(IList<T> list, int a, int b)
    {
        T temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }
}

public class Heapsort {
    public static <T extends Comparable<T>> void sort(T[] array) {
        int heapSize = array.length;
        buildHeap(array, heapSize);
        while (heapSize > 1) {
            swap(array, 0, heapSize - 1);
            heapSize--;
            heapify(array, heapSize, 0);
        }
    }

    private static <T extends Comparable<T>> void buildHeap(
            T[] array, int heapSize) {
        for (int i = (int)(array.length / 2); i >= 0; i--) {
            heapify(array, heapSize, i);
        }
    }

    private static <T extends Comparable<T>> void heapify(
            T[] array, int heapSize, int i) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int largest;
        if (left < heapSize && array[left].compareTo(array[i]) > 0)
            largest = left;
        else
            largest = i;
        if (right < heapSize && array[right].compareTo(array[largest]) > 0)
            largest = right;
        if (largest != i) {
            swap(array, i, largest);
            heapify(array, heapSize, largest);
        }
    }

    private static <T extends Comparable<T>> void swap(
            T[] array, int a, int b) {
        T temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

/**
 * Heapify an array.
 * @param {Array} array The array to build a heapify.
 * @param {number} heapSize The size of the heap.
 * @param {number} i The index of the array to heapify.
 * @param {function} compare The compare function.
 * @param {function} swap A function to call when the swap operation is
 * performed. This can be used to listen in on internals of the algorithm.
 * @returns The sorted array.
 */
function heapify(array, heapSize, i, compare, swap) {
  var left = i * 2 + 1;
  var right = i * 2 + 2;
  var largest = i;

  if (left < heapSize && compare(array, left, largest) > 0) {
    largest = left;
  }
  if (right < heapSize && compare(array, right, largest) > 0) {
    largest = right;
  }

  if (largest !== i) {
    swap(array, i, largest);
    heapify(array, heapSize, largest, compare, swap);
  }
}

/**
 * Build a heap out of an array.
 * @param {Array} array The array to build a heap on.
 * @param {number} heapSize The size of the heap.
 * @param {function} compare The compare function.
 * @param {function} swap A function to call when the swap operation is
 * performed. This can be used to listen in on internals of the algorithm.
 * @returns The sorted array.
 */
function buildHeap(array, heapSize, compare, swap) {
  for (var i = Math.floor(array.length / 2); i >= 0; i--) {
    heapify(array, heapSize, i, compare, swap);
  }
}

/**
 * Sorts an array using heapsort.
 * @param {Array} array The array to sort.
 * @param {function} compare The compare function.
 * @param {function} swap A function to call when the swap operation is
 * performed. This can be used to listen in on internals of the algorithm.
 * @returns The sorted array.
 */
function sort(array, compare, swap) {
  var heapSize = array.length;
  buildHeap(array, heapSize, compare, swap);
  while (heapSize > 1) {
    swap(array, 0, --heapSize);
    heapify(array, heapSize, 0, compare, swap);
  }
  return array;
}

def default_compare(a, b):
  if a < b:
    return -1
  elif a > b:
    return 1
  return 0

def sort(array, compare=default_compare):
  heap_size = len(array)
  build_heap(array, heap_size, compare)
  while heap_size > 1:
    heap_size -= 1
    array[0], array[heap_size] = array[heap_size], array[0]
    heapify(array, heap_size, 0, compare)
  return array

def heapify(array, heap_size, i, compare):
  left = i * 2 + 1
  right = i * 2 + 2
  largest = i
  if left < heap_size and compare(array[left], array[largest]) > 0:
    largest = left
  if right < heap_size and compare(array[right], array[largest]) > 0:
    largest = right
  if largest != i:
    array[i], array[largest] = array[largest], array[i]
    heapify(array, heap_size, largest, compare)

def build_heap(array, heap_size, compare):
  for i in range(math.floor(len(array) / 2), -1, -1):
    heapify(array, heap_size, i, compare)

module Heapsort
  # Sorts an array using heapsort.
  def self.sort(array, compare = lambda { |a, b| a <=> b })
    heap_size = array.length
    self.build_heap(array, heap_size, compare)
    while heap_size > 1
      heap_size -= 1
      array[0], array[heap_size] = array[heap_size], array[0]
      self.heapify(array, heap_size, 0, compare)
    end
  end

private

  # Heapify an array.
  def self.heapify(array, heap_size, i, compare)
    left = i * 2 + 1
    right = i * 2 + 2
    largest = i
    if left < heap_size and compare.call(array[left], array[largest]) > 0
      largest = left
    end
    if right < heap_size and compare.call(array[right], array[largest]) > 0
      largest = right
    end
    if largest != i
      array[i], array[largest] = array[largest], array[i]
      self.heapify(array, heap_size, largest, compare)
    end
  end

  # Build a heap out of an array.
  def self.build_heap(array, heap_size, compare)
    (array.length / 2).floor.downto(0) do |i|
      heapify(array, heap_size, i, compare)
    end
  end
end

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.

 

More posts tagged Sorting