Growing with the Web

Heapsort

Published , updated
Tags:

Heapsort is an O(n \log n) sorting algorithm that works by first constructing a heap out of the list and repeatedly pulling the root off the top of the heap and reconstructs it until there are no items left in the heap. The values that are pulled off of the top of the heap come out in sorted order. If the heap used was a min-heap, the resulting list will be in ascending order, and a max-heap will give them in descending order.

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

Heapsort example

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.

ary tree array representation

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

Comments

comments powered by Disqus
Like this article?
Subscribe for more!