/***************************************************************************
* Author: Isai Damier
* Title: Heapsort
* Project: geekviewpoint
* Package: algorithms
*
* Statement:
* Given a disordered list of integers (or any other items),
* rearrange the integers in natural order.
*
* Sample Input: {8,5,3,1,9,6,0,7,4,2,5}
* Sample Output: {0,1,2,3,4,5,5,6,7,8,9}
*
* Time Complexity of Solution:
* Best O(n*log(n)); Average O(n*log(n)); Worst O(n*log(n)).
*
* Approach:
* Heap sort happens in two phases. In the first phase, the array
* is transformed into a heap. A heap is a binary tree where
* 1) each node is greater than each of its children
* 2) the tree is perfectly balanced
* 3) all leaves are in the leftmost position available.
* In phase two the heap is continuously reduced to a sorted array:
* 1) while the heap is not empty
* - remove the top of the head into an array
* - fix the heap.
* Heap sort was invented by John Williams not by B. R. Heap.
*
* MoveDown:
* The movedown method checks and verifies that the structure is a heap.
*
* Technical Details:
* A heap is based on an array just as a hashmap is based on an
* array. For a heap, the children of an element n are at index
* 2*n+1 for the left child and 2*n+2 for the right child.
*
* The movedown function checks that an element is greater than its
* children. If not the values of element and child are swapped. The
* function continues to check and swap until the element is at a position
* where it is greater than its children.
***************************************************************************/
public void heapsort(int[] input) {
// convert input to heap
int leastParent = (input.length - 1) / 2;
for (int i = leastParent; i >= 0; i--) {
moveDown(input, i, input.length - 1);
}
// flatten heap into sorted array
for (int i = input.length - 1; i > 0; i--) {
if (input[0] > input[i]) {
swap(input, 0, i);
moveDown(input, 0, i - 1);
}
}
}
private void moveDown(int[] input, int first, int last) {
int largest = 2 * first + 1;
while (largest <= last) {
// right child exists and is larger than left child
if (largest < last && input[largest] < input[largest + 1]) {
largest++;
}
// right child is larger than parent
if (input[largest] > input[first]) {
swap(input, largest, first);
// move down to largest child
first = largest;
largest = 2 * first + 1;
} else {
return;// force exit
}
}
}
private void swap(int[] input, int a, int b) {
int tmp = input[a];
input[a] = input[b];
input[b] = tmp;
}
import org.junit.Test;
import static org.junit.Assert.*;
public class SortingTest {
@Test
public void testHeapsort() {
System.out.println(""heapsort"");
int[] input = {8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5};
Sorting instance = new Sorting();
instance.heapsort(input);
for (int i = 1; i < input.length; i++) {
if (input[i - 1] > input[i]) {
fail(""heapsort method fails."");
}
}
}
}