# Difference between revisions of "Heapsort"

 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

### 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 */
} 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(a); // [-8,0,1,3,11,35,68]
}
```

### 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
* 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: ' );
// 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]
```

### 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
array.unshift nil         # heap root [0]=>[1]
(n / 2).downto(1) do |i|
down_heap(array, i, n)
end
while n > 1
array[1], array[n] = array[n], array[1]
n -= 1
down_heap(array, 1, n)
end
array.shift               # 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 = [-8,0,1,3,11,35,68]
heap_sort(a)
p 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]