Algorithm Implementation/Sorting/Heapsort
Basic heapsort
editWith 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
editThe 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
editfunction 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