Algorithm Implementation/Sorting/Heapsort

Basic heapsort

edit

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

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
    sift-down (a start end)
  "Sifts 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)
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();
    
}
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

edit

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.

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) 
{
    if(N==0) // check if heap is empty
      return;

    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; 
    }
}
#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);
}
/**
 * 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
                }
              }
            }
        }
    }
}
}
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

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|]
const maxA = 1000;
type TElem = integer;
     TArray = array[1..maxA]of TElem;

procedure heapify(var A:TArray;i,heapSize:integer);
var l,r,largest,save:integer;
    t:TElem;
begin
  repeat
     l := 2 * i;
     r := 2 * i + 1;
     if(l <= heapSize)and(A[l] > A[i])then
         largest := l
     else 
         largest := i;
     if(r <= heapSize)and(A[r] > A[largest])then
        largest := r;
     save := i;
     if largest <> i then
     begin
       t := A[i];
       A[i] := A[largest];
       A[largest] := t;
       i := largest;  
     end;
  until largest = save;
end;

procedure buildHeap(var A:TArray;n:integer);
var i:integer;
begin
  for i := n div 2 downto 1 do 
     heapify(A,i,n);
end;

procedure heapSort(var A:TArray;n:integer);
var i:integer;
    t:TElem;
begin
  buildHeap(A,n);
  for i := n downto 2 do
  begin
    t := A[1];
    A[1] := A[i];
    A[i] := t;
    heapify(A,1,i - 1);
  end;
end;

Phix

edit
function siftDown(sequence arr, integer s, integer last)
integer root = s
    while root*2<=last do
        integer child = root*2 
        if child<last and arr[child]<arr[child+1] then
            child += 1
        end if
        if arr[root]>=arr[child] then exit end if
        object tmp = arr[root]
        arr[root] = arr[child]
        arr[child] = tmp
        root = child
    end while
    return arr
end function
 
function heapify(sequence arr, integer count)
integer s = floor(count/2)
    while s>0 do
        arr = siftDown(arr,s,count)
        s -= 1
    end while
    return arr
end function
 
function heap_sort(sequence arr)
integer last = length(arr)
    arr = heapify(arr,last)
    while last>1 do
        object tmp = arr[1]
        arr[1] = arr[last]
        arr[last] = tmp
        last -= 1
        arr = siftDown(arr,1,last)
    end while
    return arr
end function