Algorithm Implementation/Sorting/Heapsort

Basic heapsort

With an existing heap data structure, a basic heapsort is simple to implement.

Common Lisp

This is an almost direct translation of the heapsort pseudocode found at Wikipedia, taking a list of scalars as input.

(define macro
  troca (left right)
  "Swap left and right values."
  `(let
    ((tmp))
    (setf tmp ,right)
    (setf ,right ,left)
    (setf ,left tmp)))
 
(define
    shift-down (a start end)
  "Shifts the elements down the heap."
  (let ((root start)
        (child)
        (swap))
    (loop
      (if (<= (+ (* root 2) 1) end)
          (progn
           (setf child (+ (* root 2) 1))
           (setf swap root)
           (if (< (nth swap a) (nth child a))
               (setf swap child))
           (if (and (< child end) (< (nth swap a) (nth (+ child 1) a)))
               (setf swap (+ child 1)))
           (if (not (eql swap root))
               (progn
                (troca (nth root a) (nth swap a))
                (setf root swap))
             (return-from sift-down)))
        (return)))))
 
(define
    heapify (a)
  "Makes the input list a heap by repeatedly sifting down."
  (let*
      ( (cnt (length a))
       (start (- (ceiling (/ cnt 2)) 1)))
    (loop
      (if (>= start 0)
          (progn
           (sift-down a start (- cnt 1))
           (decf start))
        (return)))))
(define
    heapsort (lista)
  "Iterative heapsort. The argument lista is a list. Example usage: (heapsort '(1 3 4 2 9 2 5 3))"
  (let*
      ( (cnt (length lista))
       (end (- cnt 1)))
    (heapify lista)
    (loop
      (if (> end 0)
          (progn
           (troca (nth end lista) (nth 0 lista))
           (sift-down lista 0 (- end 1))
           (decf end))
        (return)))) lista)

Java

import java.util.PriorityQueue;
public static <E extends Comparable<? super E>> void heapsort(E[] array) {
 
    // Java's PriorityQueue class functions as a min heap
    PriorityQueue<E> heap = new PriorityQueue<E>(array.length);
 
    // Add each array element to the heap
    for (E e : array)
        heap.add(e);
 
    // Elements come off the heap in ascending order
    for (int i=0; i<array.length; i++)
        array[i] = heap.remove();
 
}

Python

import heapq
def heapsort(lst):
    # Copy the list into a temporary list
    heap = list(lst)
 
    # Make it into a heap
    heapq.heapify(heap)
 
    # Elements come off the heap in ascending order
    for i in xrange(len(lst)):
        lst[i] = heapq.heappop(heap)

In-place heapsort

The disadvantage of the basic method is its memory requirement; it requires both an array and a heap of size n.

If we realize that heaps can be stored as arrays, a solution presents itself: Store the heap in the same array as the unsorted/sorted elements.

C

This is a fast implementation of heapsort in C, adapted from Numerical Recipes in C but designed to be slightly more readable and to index from 0.

void heapsort(int arr[], unsigned int N) 
{
    int t; /* the temporary value */
    unsigned int n = N, parent = N/2, index, child; /* heap indexes */
    /* loop until array is sorted */
    while (1) { 
        if (parent > 0) { 
            /* first stage - Sorting the heap */
            t = arr[--parent];  /* save old value to t */
        } else {
            /* second stage - Extracting elements in-place */
            n--;                /* make the heap smaller */
            if (n == 0) {
                return; /* When the heap is empty, we are done */
            }
            t = arr[n];         /* save lost heap entry to temporary */
            arr[n] = arr[0];    /* save root entry beyond heap */
        }
        /* insert operation - pushing t down the heap to replace the parent */
        index = parent; /* start at the parent index */
        child = index * 2 + 1; /* get its left child index */
        while (child < n) {
            /* choose the largest child */
            if (child + 1 < n  &&  arr[child + 1] > arr[child]) {
                child++; /* right child exists and is bigger */
            }
            /* is the largest child larger than the entry? */
            if (arr[child] > t) {
                arr[index] = arr[child]; /* overwrite entry with child */
                index = child; /* move index to the child */
                child = index * 2 + 1; /* get the left child and go around again */
            } else {
                break; /* t's place is found */
            }
        }
        /* store the temporary value at its new location */
        arr[index] = t; 
    }
}

C++

#include <algorithm> // for std::make_heap, std::sort_heap
 
template <typename Iterator>
void heap_sort(Iterator begin, Iterator end)
{
    std::make_heap(begin, end);
    std::sort_heap(begin, end);
}

Java

/**
 * Heapsort for sorting an array of integers.
 * @param array the array to be sorted
 */
public static void heapSort(int[] array) {
    /* This method performs an in-place heapsort. Starting
     * from the beginning of the array, the array is swapped
     * into a binary max heap.  Then elements are removed
     * from the heap, and added to the front of the sorted
     * section of the array. */
 
    /* Insertion onto heap */
    for (int heapsize=0; heapsize<array.length; heapsize++) {
        /* Step one in adding an element to the heap in the
         * place that element at the end of the heap array-
         * in this case, the element is already there. */
        int n = heapsize; // the index of the inserted int
        while (n > 0) { // until we reach the root of the heap
            int p = (n-1)/2; // the index of the parent of n
            if (array[n] > array[p]) { // child is larger than parent
                arraySwap(array, n, p); // swap child with parent
                n = p; // check parent
            }
            else // parent is larger than child
                break; // all is good in the heap
        }
    }
 
    /* Removal from heap */
    for (int heapsize=array.length; heapsize>0;) {
        arraySwap(array, 0, --heapsize); // swap root with the last heap element
        int n = 0; // index of the element being moved down the tree
        while (true) {
            int left = (n*2)+1;
            if (left >= heapsize) // node has no left child
                break; // reached the bottom; heap is heapified
            int right = left+1;
            if (right >= heapsize) { // node has a left child, but no right child
                if (array[left] > array[n]) // if left child is greater than node
                    arraySwap(array, left, n); // swap left child with node
                break; // heap is heapified
            }
            if (array[left] > array[n]) { // (left > n)
                if (array[left] > array[right]) { // (left > right) & (left > n)
                    arraySwap(array, left, n);
                    n = left; continue; // continue recursion on left child
                } else { // (right > left > n)
                    arraySwap(array, right, n);
                    n = right; continue; // continue recursion on right child
                }
            } else { // (n > left)
                if (array[right] > array[n]) { // (right > n > left)
                    arraySwap(array, right, n);
                    n = right; continue; // continue recursion on right child
                } else { // (n > left) & (n > right)
                    break; // node is greater than both children, so it's heapified
                }
            }
        }
    }
}

Ruby

module HeapSort
  def self.sort(keys)
    sort!(keys.clone)
  end
 
  def self.sort!(keys)
    build_max_heap(keys)
    (keys.size-1).downto(1) do |i|
      keys[0], keys[i] = keys[i], keys[0]
      max_heapify(keys, i, 0)
    end
    keys
  end
 
  private
 
  def self.build_max_heap(keys)
    (keys.size/2-1).downto(0) do |i|
      max_heapify(keys, keys.size, i)
    end
    keys
  end
 
  def self.max_heapify(keys, size, i)
    l = 2*i+1
    r = 2*i+2
    if l < size and keys[l] > keys[i]
      largest = l 
    else 
      largest = i
    end
    if r < size and keys[r] > keys[largest]
      largest = r 
    end
    if (largest != i)
      keys[i], keys[largest] = keys[largest], keys[i]
      max_heapify(keys, size, largest)
    end
  end
end

Ocaml

This implementation is in place and uses the imperative features of the language such as loops and mutable reference cells.

let swap a i j =
  let temp = a.(i) in
  a.(i) <- a.(j);
  a.(j) <- temp
 
let sift a start count =
  let root = ref start
  and child = ref (start * 2 + 1) in
 
  while !root * 2 + 1 < count do
    if !child < count - 1 && a.(!child) < a.(!child + 1)
      then incr child;
 
    if a.(!root) < a.(!child) then begin
      swap a !root !child;
      root := !child
    end else (* Terminate Loop *) root := count;
 
    child := !root * 2 + 1
  done
 
let heapsort a count =
  for start = count/2 - 1 downto 0 do
    sift a start count
  done;
 
  for term = count - 1 downto 1 do
    swap a term 0;
    sift a 0 term
  done

Example of use:

 # let a = [|4;45;67;4;2;2;3;4;6;8;9;9;7;5;4;32;3;4;5;6;6;4;3;2;3;5;7;8;9;8;7;6;54|] in heapsort a (Array.length a); a;;
 - : int array =
   [|2; 2; 2; 3; 3; 3; 3; 4; 4; 4; 4; 4; 4; 5; 5; 5; 6; 6; 6; 6; 7; 7; 7; 8; 8; 8; 9; 9; 9; 32; 45; 54; 67|]