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.

Implementations[edit]

Pseudocode[edit]

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++[edit]

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++[edit]

#include <algorithm>

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

Common Lisp[edit]

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

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

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

Implementation 1[edit]

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

/*
 * @(#)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[edit]

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

(** 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[edit]

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

/* ------------------------------------------------------------------ */
/* 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[edit]

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

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]