Heapsort

From CodeCodex

Related content:

Heapsort is one of the best general-purpose sort algorithms, a comparison sort and part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime and being an in-place algorithm. Heapsort is not a stable sort.

Contents

Implementations

Pseudocode

The following is one way to implement the algorithm, in pseudocode, where swap is used to swap two elements of the array. Notice that the arrays are zero-based in this example.

 function heapSort(a, count) {
     var int start := count ÷ 2 - 1,
           end := count - 1

     while start ≥ 0
         sift(a, start, count)
         start := start - 1

     while end > 0
         swap(a[end], a[0])
         sift(a, 0, end)
         end := end - 1
 }
 
 function sift(a, start, count) {
     var int root := start, child

     while root * 2 + 1 < count {
         child := root * 2 + 1
         if child < count - 1 and a[child] < a[child + 1]
             child := child + 1
         if a[root] < a[child]
             swap(a[root], a[child])
             root := child
         else
             return
     }
 }

C/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)
  {
      unsigned int n = N, i = n/2, parent, child;
      int t;
  
      for (;;) { /* Loops until arr is sorted */
          if (i > 0) { /* First stage - Sorting the heap */
              i--;           /* Save its index to i */
              t = arr[i];    /* Save parent value to t */
          } else {     /* Second stage - Extracting elements in-place */
              n--;           /* Make the new heap smaller */
              if (n == 0) return; /* When the heap is empty, we are done */
              t = arr[n];    /* Save last value (it will be overwritten) */
              arr[n] = arr[0]; /* Save largest value at the end of arr */
          }
  
          parent = i; /* We will start pushing down t from parent */
          child = i*2 + 1; /* parent's left child */
  
          /* Sift operation - pushing the value of t down the heap */
          while (child < n) {
              if (child + 1 < n  &&  arr[child + 1] > arr[child]) {
                  child++; /* Choose the largest child */
              }
              if (arr[child] > t) { /* If any child is bigger than the parent */
                  arr[parent] = arr[child]; /* Move the largest child up */
                  parent = child; /* Move parent pointer to this child */
                  //child = parent*2-1; /* Find the next child */
                  child = parent*2+1; /* the previous line is wrong*/
              } else {
                  break; /* t's place is found */
              }
          }
          arr[parent] = t; /* We save t in the heap */
      }
  }

C++

#include <algorithm>

template <typename Iterator>
void heapsort(Iterator begin, Iterator end) {
    std::make_heap(begin, end);
    std::sort_heap(begin, end);
}

Common Lisp

This version mostly follows the pseudo-code.

 (defun heap-sort (a &optional (count (length a)))
   (macrolet ((ref (i) `(aref a ,i))
              (swap (i j) `(rotatef (ref ,i) (ref ,j)))
              (ref< (i j) `(< (ref ,i) (ref ,j))))
 
     (labels ((sift (root count)
                (let ((c1 (+ (* 2 root) 1))
                      (c2 (+ (* 2 root) 2)))
                  (when (< c1 count)
                    (let ((c (if (and (< c2 count) (ref< c1 c2)) c2 c1)))
                      (when (ref< root c)
                        (swap root c)
                        (sift c count)))))))
 
       (loop for start from (1- (floor count 2)) downto 0
             do (sift start count))
 
       (loop for end from (1- count) downto 1
             do (swap 0 end) (sift 0 end))))
 
   a)

D

This version comes directly from the pseudocode and the Python version, but a faster version quite close to the C one is possible too. In D you usually use the array .sort method.

 import std.stdio;
 
 void heapSort(T)(T[] a) {
     void swap(int i, int j) {
         T aux = a[i];
         a[i] = a[j];
         a[j] = aux;
     }
 
     void sift(int start, int count) {
         int root = start;
 
         while (root * 2 + 1 < count) {
             int child = root * 2 + 1;
             if (child < count - 1 && a[child] < a[child + 1])
                 child++;
             if (a[root] < a[child]) {
                 swap(root, child);
                 root = child;
             } else
                 return;
         }
     }
 
     int count = a.length;
     int start = count / 2 - 1;
     int end = count - 1;
 
     while (start >= 0) {
         sift(start, count);
         start--;
     }
 
     while (end > 0) {
         swap(end, 0);
         sift(0, end);
         end--;
     }
 }
 
 void main() {
     auto a = [35, -8, 11, 1, 68, 0, 3];
     heapSort(a);
     writefln("%s",a); // [-8,0,1,3,11,35,68]
 }

Erlang

used process dictionary

heap_sort([]) -> [];
heap_sort(L) ->
    Size = length(L),
    lists:foldl(fun(X, I) -> put(I, X), I+1 end, 1, L),
    lists:foreach(fun(I) -> make_heap(I, get(I)) end, lists:seq(2, Size)),
    lists:foreach(fun(I) -> down_heap(I) end, lists:seq(Size, 2, -1)),
    lists:foldl(fun(I, R) -> [get(I)|R] end, [], lists:seq(Size, 1, -1)).

make_heap(I, A) ->
    J = I div 2,
    B = get(J),
    if  J<1 orelse A=<B -> put(I, A);
        true            -> put(I, B),
                           make_heap(J, A)
    end.

down_heap(I) ->
    Root = 1,
    Val = put(I, put(Root, get(I))),     % exchange Root <-> I
    down_heap(I-1, Root, 2*Root, Val).

down_heap(Limit, Parent, Child, Val) when Limit < Child ->
    put(Parent, Val);
down_heap(Limit, Parent, Child, Val) ->
    V0 = get(Child),
    V1 = get(Child+1),
    {C, V} = if  Child < Limit andalso V0 < V1 -> {Child+1, V1};
                 true                          -> {Child,   V0}
             end,
    if  Val >= V -> put(Parent, Val);
        true     -> put(Parent, V),
                    down_heap(Limit, C, 2*C, Val)
    end.

Java

Implementation 1

public class HeapSort
{
    public static <T extends Comparable<? super T>> void sort(T[] table)
    {
        buildHeap(table);
        shrinkHeap(table);
    }

    private static <T extends Comparable<? super T>> void buildHeap(T[] table)
    {
        for (int child = 1; child < table.length; child++)
        {
            int parent = (child - 1) / 2;
            while (parent >= 0 && table[parent].compareTo(table[child]) < 0)
            {
                swap(table, parent, child);
                child = parent;
                parent = (child - 1) / 2;
            }
        }
    }

    private static <T extends Comparable<? super T>> void shrinkHeap(T[] table)
    {
        for (int n = table.length-1; n >= 0; n--)
        {
            swap(table, 0, n);
            int parent = 0;
            while (true)
            {
                int leftChild = 2 * parent + 1;
                if (leftChild >= n)
                    break; // no more children
                int rightChild = leftChild + 1;
                int maxChild = leftChild;
                if (rightChild < n && table[leftChild].compareTo(table[rightChild]) < 0)
                    maxChild = rightChild;
                if (table[parent].compareTo(table[maxChild]) < 0)
                {
                    swap(table, parent, maxChild);
                    parent = maxChild;
                }
                else
                    break; // exit loop
            }
        }
    }

    private static void swap(Object[] table, int i, int j)
    {
        Object temp = table[i];
        table[i] = table[j];
        table[j] = temp;
    }
}

Implementation 2

/*
 * @(#)HeapSortAlgorithm.java	1.0 95/06/23 Jason Harrison
 *
 * Copyright (c) 1995 University of British Columbia
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL purposes and without
 * fee is hereby granted provided that this copyright notice
 * appears in all copies. Please refer to the file "copyright.html"
 * for further important copyright and licensing information.
 *
 * UBC MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. UBC SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 */

/**
 * A heap sort demonstration algorithm
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
 *
 * @author Jason Harrison@cs.ubc.ca
 * @version 	1.0, 23 Jun 1995
 */
class HeapSortAlgorithm extends SortAlgorithm {
    void sort(int a[]) throws Exception {
	int N = a.length;
	for (int k = N/2; k > 0; k--) {
	    downheap(a, k, N);
	    pause();
        }
	do {
            int T = a[0];
            a[0] = a[N - 1];
            a[N - 1] = T;
	    N = N - 1;
	    pause(N);
            downheap(a, 1, N);
	} while (N > 1);
    }

    void downheap(int a[], int k, int N) throws Exception {
	int T = a[k - 1];
	while (k <= N/2) {
            int j = k + k;
            if ((j < N) && (a[j - 1] < a[j])) {
	        j++;
	    }
	    if (T >= a[j - 1]) {
		break;
	    } else {
                a[k - 1] = a[j - 1];
                k = j;
		pause();
            }
	}
        a[k - 1] = T;
	pause();
    }
}

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|]

Pascal

(** Heap sort algorithm.
*
* Author: Paulo Roma
* Date: 22/04/2008.
* http://en.wikipedia.org/wiki/Heapsort
* http://www2.hawaii.edu/~copley/665/HSApplet.html
*)

program Heap_Sort;

type SArray = array of integer;
var Asize: integer;
var A: SArray;
var i: integer;

(** swap.
*
* Swaps two given values.
*
* @param a,b values to be swaped.
*)

procedure swap ( var a, b: integer );
var temp: integer;
begin
temp := a;
a := b;
b := temp;
end;

(** siftDown.
*
* Sifts downward to establish the heap property.
*
* @param A array.
* @param start heap root.
* @param end_ represents the limit of how far down the heap to sift.
*)

procedure siftDown ( var A: SArray; start, end_: integer );
var root, child: integer;
begin
root := start;

// While the root has at least one child
while ( root * 2 + 1 <= end_ ) do begin 
child := root * 2 + 1; // left child
// If the child has a sibling and
// the child's value is less than its sibling's
if ( child < end_ ) and ( A[child] < A[child + 1] ) then
child := child + 1; // point to the right child instead
if ( A[root] < A[child] ) then begin // out of max-heap order
swap ( A[root], A[child] );
root := child; // repeat to continue sifting down the child
end
else
break;
end;
end;

(** heapify.
*
* Builds a heap from the bottom up.
*
* The heapify function can be thought of as building a
* heap from the bottom up, successively sifting downward
* to establish the heap property.
*
* @param A array.
* @param count number of elements in A.
*)

procedure heapify ( var A: SArray; count: integer );
var start: integer;
begin
// start is assigned the index in A of the last parent node
start := (count - 1) div 2;

while ( start >= 0 ) do begin
// sift down the node at start index to the proper place,
// such that all nodes below the start index are in heap order
siftDown (A, start, count-1);
start := start - 1;
// after sifting down the root all nodes/elements are in heap order
end;
end;

(** heapSort.
*
* Sorts A=(A0, A1, ..., An) into nondecreasing order of keys.
* This algorithm has a worst case computational time of O(n log n).
* Not stable.
*
* Heapsort primarily competes with quicksort,
* another very efficient, general purpose, and
* nearly-in-place, comparison-based sort algorithm.
*
* Heapsort inserts the input list elements into a heap data structure.
* The largest value (in a max-heap) or the smallest value
* (in a min-heap) are extracted until none remain,
* the values being extracted in sorted order.
* The heap's invariant is preserved after each
* extraction, so the only cost is that of extraction.
*
* During extraction, the only space required is that needed to store
* the heap. In order to achieve constant space overhead, the heap
* is stored in the part of the input array that has not yet been sorted.
* (The structure of this heap is described at Binary heap:
* Heap implementation.)
*
* Heapsort uses two heap operations: insertion and root deletion.
* Each extraction places an element in the last empty location of
* the array. The remaining prefix of the array stores the
* unsorted elements.
*
* @param A array to be sorted.
* @param n number of elements to be sorted.
*)

procedure heapSort( var A: SArray; n: integer );
var end_: integer;
begin
// first place A in max-heap order
heapify ( A, n );

end_ := n - 1;
while ( end_ > 0 ) do begin
// swap the root (maximum value) of the heap
// with the last element of the heap
swap( A[end_], A[0]);
// decrease the size of the heap by one,
// so that the previous max value
// will stay in its proper placement
end_ := end_ - 1;
// put the heap back in max-heap order
siftDown (A, 0, end_);
end;
end;

begin
write ( 'Enter number of elements: ' );
read ( Asize );
// alocate an array from 0 to Asize-1
// the array index is always zero-based
SetLength ( A, Asize );
// generate the seed
randomize;
// fill A with random numbers in the range [0..99]
for i := 0 to Asize-1 do
A[i] := random (100);

// print original array
for i := 0 to Asize-1 do begin
write (A[i]); write (' ');
end;
writeln;

// sort
heapSort ( A, Asize );

// print sorted array
for i := 0 to Asize-1 do begin
write (A[i]); write (' ');
end;
writeln;
end.

Python

This version comes directly from the pseudocode, a version like the C one is possible too. Usually in Python you use the built-in sort/sorted.

 def heapSort(a):
     def sift(start, count):
         root = start
 
         while root * 2 + 1 < count:
             child = root * 2 + 1
             if child < count - 1 and a[child] < a[child + 1]:
                 child += 1
             if a[root] < a[child]:
                 a[root], a[child] = a[child], a[root]
                 root = child
             else:
                 return
 
     count = len(a)
     start = count / 2 - 1
     end = count - 1
 
     while start >= 0:
         sift(start, count)
         start -= 1
 
     while end > 0:
         a[end], a[0] = a[0], a[end]
         sift(0, end)
         end -= 1
 
 a = [-8,0,1,3,11,35,68]
 heapSort(a)
 print a # [-8, 0, 1, 3, 11, 35, 68]

Recursive sift(and more readable IMHO) Version:

def heapsort(a):

    def swap(a,i,j):
        tmp = a[i]
        a[i] = a[j]
        a[j] = tmp  
        
    def siftdown(a, i, size):
        l = 2*i+1
        r = 2*i+2
        largest = i
        if l <= size-1 and a[l] > a[i]:
            largest = l
        if r <= size-1 and a[r] > a[largest]:
            largest = r
        if largest != i:
            swap(a, i, largest)
            siftdown(a, largest, size)
            
    def heapify(a, size):
        p = (size/2)-1
        while p>=0:
            siftdown(a, p, size)
            p -= 1
            
    size = len(a)        
    heapify(a, size)
    end = size-1
    while(end > 0):
        swap(a, 0, end)
        siftdown(a, 0, end)
        end -= 1

Rexx

/* ------------------------------------------------------------------ */
/* function: heap sort routine                                        */
/*                                                                    */
/* call:     HeapSort                                                 */
/*                                                                    */
/* returns:  nothing                                                  */
/*                                                                    */
/* notes:    You must save the elements to sort in the stem "STEM."   */
/*           stem.0 must contain the number of elements in the stem.  */
/*                                                                    */
/* reference: Sedgewick, "Algorithms"                                 */
/*                                                                    */
Heapsort: PROCEDURE expose stem.

  M = stem.0
  N = M

  do k=M % 2 to 1 by -1
    call DownHeap k N
  end /* do */

  do while N>1
    t = stem.1
    stem.1 = stem.n
    stem.n = t
    n = n-1
    call DownHeap 1 N
  end /* do */
RETURN

/* subroutine of HeapSort                                             */
DownHeap: PROCEDURE expose stem.
  parse Arg k N

  v = stem.k

  do while k <= N%2
    j = k+k
    if j < n then
    do
      i = j+1
      if stem.j << stem.i then                               /* v2.80 */
        j=j+1
    end  /* do */

    if v >>= stem.j then                                     /* v2.80 */
      signal Label

    stem.k = stem.j
    k = j
  end /* do */

Label:
  stem.k = v
RETURN

Ruby

def heap_sort(array)
  n = array.size
  a = [nil] + array             # heap root [0]=>[1]
  (n / 2).downto(1) do |i|
    down_heap(a, i, n)
  end
  while n > 1
    a[1], a[n] = a[n], a[1]
    n -= 1
    down_heap(a, 1, n)
  end
  a.drop(1)                     # heap root [1]=>[0]
end

def down_heap(a, parent, limit)
  wk = a[parent]
  while (child = 2 * parent) <= limit
    child += 1  if child < limit and a[child] < a[child + 1]
    break  if wk >= a[child]
    a[parent] = a[child]
    parent = child
  end
  a[parent] = wk
end

a = [35, -8, 11, 1, 68, 0, 3]
p heap_sort(a)    #=> [-8, 0, 1, 3, 11, 35, 68]

Seed7

const proc: downheap (inout array elemType: arr, in var integer: k, in integer: n) is func
  local
    var elemType: help is elemType.value;
    var integer: j is 0;
  begin
    if k <= n div 2 then
      help := arr[k];
      repeat
        j := 2 * k;
        if j < n and arr[j] < arr[succ(j)] then
          incr(j);
        end if;
        if help < arr[j] then
          arr[k] := arr[j];
          k := j;
        end if;
      until help >= arr[j] or k > n div 2;
      arr[k] := help;
    end if;
  end func;

const proc: heapSort (inout array elemType: arr) is func
  local
    var integer: n is 0;
    var integer: k is 0;
    var elemType: help is elemType.value;
  begin
    n := length(arr);
    for k range n div 2 downto 1 do
      downheap(arr, k, n);
    end for;
    repeat
      help := arr[1];
      arr[1] := arr[n];
      arr[n] := help;
      decr(n);
      downheap(arr, 1, n);
    until n <= 1;
  end func;

Original source: [1]