This implementation comes from
en.wikipedia.org.
The outer loop runs O(n) times and the inner loop is O(log n) so the whole algorithm is O(n log n).
In general, quicksort would be faster to implement in practice because heapsort is actually not a divide and conquer algorithm, which is true O(log n).
Here, we implemented the sift down method which repairs a broken heap. This is O(n/2*2) since the inner loop iterates through all parent nodes (only half the nodes) but compares to both children. The number of parent nodes decreases by 1 each time the inner loop executes. This implementation is O(n^2/2) = O(n^2).
--------
-------
------
-----
----
---
--
-
package algorithm;
public class heapsort {
public static void main(String[] args) {
System.out.println("Case I");
int[] numbers = new int[] {3, 7, 8, 5, 2, 1, 9, 5, 4};
printArrayAndHeap(0, numbers.length - 1, numbers, "pre_sort");
heapsort(numbers);
printArrayAndHeap(0, numbers.length - 1, numbers, "post_sort");
System.out.println("Case II");
numbers = new int[] {9, 8, 7, 6, 5, 4, 3, 2, 1};
printArrayAndHeap(0, numbers.length - 1, numbers, "pre_sort");
heapsort(numbers);
printArrayAndHeap(0, numbers.length - 1, numbers, "post_sort");
System.out.println("Case III");
numbers = new int[] {5, 5, 5, 5, 5, 5, 5, 5, 5};
printArrayAndHeap(0, numbers.length - 1, numbers, "pre_sort");
heapsort(numbers);
printArrayAndHeap(0, numbers.length - 1, numbers, "post_sort");
System.out.println("Case IV");
numbers = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
printArrayAndHeap(0, numbers.length - 1, numbers, "pre_sort");
heapsort(numbers);
printArrayAndHeap(0, numbers.length - 1, numbers, "post_sort");
}
private static void printArrayAndHeap(int i, int j, int[] numbers, String text) {
printArray(i,j,numbers, text);
printHeap(i,j,numbers);
}
private static void printArray(int start, int end, int[] numbers, String text) {
String out = "{";
String del = "";
for(int i=start; i < end + 1; i++) {
out = out + del + numbers[i] + "";
del = ",";
}
out = out + "}";
System.out.println(text+":"+out);
}
private static void printHeap(int start, int end, int[] numbers) {
int depth = (int) Math.ceil((Math.log(end+2)/Math.log(2)));
int currentLevel = 0;
while(currentLevel < depth) {
int firstAtCurrentLevel = (int) Math.pow(2, currentLevel) - 1;
int firstAtNextLevel = (int) Math.pow(2, currentLevel + 1) - 1;
String heapout = "";
for(int index = firstAtCurrentLevel; index < firstAtNextLevel; index++) {
if(index <= end) {
heapout = heapout + " " + numbers[index];
}
}
System.out.println("level:"+currentLevel+" heap:"+heapout);
currentLevel++;
}
}
// O(n^2)
private static void heapsort(int[] numbers) {
// O(n) on outer loop
for(int i=0; i<numbers.length; i++) {
bubbleUpLargestAndPlaceAtEnd(0, numbers.length - 1 - i, numbers);
}
}
private static void bubbleUpLargestAndPlaceAtEnd(int start, int end, int[] numbers) {
if(end == 0) {
return;
}
int startingIndex = (int) Math.floor(end+1/2) - 1;
// O(n) on inner loop - Though n decreases - Fixing broken heap is O(n)
for(int i=startingIndex; i > -1; i--) {
swapParentWithLargestChild(start, end, numbers, i);
}
// Move largest from 0th place to end of array
int largest = numbers[start];
int last = numbers[end];
numbers[end] = largest;
numbers[start] = last;
printArrayAndHeap(start, end, numbers, "put_largest_at_end");
}
private static void swapParentWithLargestChild(int start, int end,
int[] numbers, int i) {
int parent = numbers[i];
if(i*2 + 2 <= end) {
int rightChild = numbers[i*2 + 2];
if(rightChild > parent) {
numbers[i] = rightChild;
numbers[i*2 + 2] = parent;
parent = rightChild;
printArrayAndHeap(start, end, numbers, "swap_right_child");
}
}
if(i*2 + 1 <= end) {
int leftChild = numbers[i*2 + 1];
if(leftChild > parent) {
numbers[i] = leftChild;
numbers[i*2 + 1] = parent;
printArrayAndHeap(start, end, numbers, "swap_left_child");
}
}
}
}
Output
Case I
pre_sort:{3,7,8,5,2,1,9,5,4}
level:0 heap: 3
level:1 heap: 7 8
level:2 heap: 5 2 1 9
level:3 heap: 5 4
swap_right_child:{3,7,9,5,2,1,8,5,4}
level:0 heap: 3
level:1 heap: 7 9
level:2 heap: 5 2 1 8
level:3 heap: 5 4
swap_right_child:{9,7,3,5,2,1,8,5,4}
level:0 heap: 9
level:1 heap: 7 3
level:2 heap: 5 2 1 8
level:3 heap: 5 4
put_largest_at_end:{4,7,3,5,2,1,8,5,9}
level:0 heap: 4
level:1 heap: 7 3
level:2 heap: 5 2 1 8
level:3 heap: 5 9
swap_right_child:{4,7,8,5,2,1,3,5}
level:0 heap: 4
level:1 heap: 7 8
level:2 heap: 5 2 1 3
level:3 heap: 5
swap_right_child:{8,7,4,5,2,1,3,5}
level:0 heap: 8
level:1 heap: 7 4
level:2 heap: 5 2 1 3
level:3 heap: 5
put_largest_at_end:{5,7,4,5,2,1,3,8}
level:0 heap: 5
level:1 heap: 7 4
level:2 heap: 5 2 1 3
level:3 heap: 8
swap_left_child:{7,5,4,5,2,1,3}
level:0 heap: 7
level:1 heap: 5 4
level:2 heap: 5 2 1 3
put_largest_at_end:{3,5,4,5,2,1,7}
level:0 heap: 3
level:1 heap: 5 4
level:2 heap: 5 2 1 7
swap_right_child:{4,5,3,5,2,1}
level:0 heap: 4
level:1 heap: 5 3
level:2 heap: 5 2 1
swap_left_child:{5,4,3,5,2,1}
level:0 heap: 5
level:1 heap: 4 3
level:2 heap: 5 2 1
put_largest_at_end:{1,4,3,5,2,5}
level:0 heap: 1
level:1 heap: 4 3
level:2 heap: 5 2 5
swap_left_child:{1,5,3,4,2}
level:0 heap: 1
level:1 heap: 5 3
level:2 heap: 4 2
swap_right_child:{3,5,1,4,2}
level:0 heap: 3
level:1 heap: 5 1
level:2 heap: 4 2
swap_left_child:{5,3,1,4,2}
level:0 heap: 5
level:1 heap: 3 1
level:2 heap: 4 2
put_largest_at_end:{2,3,1,4,5}
level:0 heap: 2
level:1 heap: 3 1
level:2 heap: 4 5
swap_left_child:{2,4,1,3}
level:0 heap: 2
level:1 heap: 4 1
level:2 heap: 3
swap_left_child:{4,2,1,3}
level:0 heap: 4
level:1 heap: 2 1
level:2 heap: 3
put_largest_at_end:{3,2,1,4}
level:0 heap: 3
level:1 heap: 2 1
level:2 heap: 4
put_largest_at_end:{1,2,3}
level:0 heap: 1
level:1 heap: 2 3
swap_left_child:{2,1}
level:0 heap: 2
level:1 heap: 1
put_largest_at_end:{1,2}
level:0 heap: 1
level:1 heap: 2
post_sort:{1,2,3,4,5,5,7,8,9}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 4 5 5 7
level:3 heap: 8 9
Case II
pre_sort:{9,8,7,6,5,4,3,2,1}
level:0 heap: 9
level:1 heap: 8 7
level:2 heap: 6 5 4 3
level:3 heap: 2 1
put_largest_at_end:{1,8,7,6,5,4,3,2,9}
level:0 heap: 1
level:1 heap: 8 7
level:2 heap: 6 5 4 3
level:3 heap: 2 9
swap_right_child:{7,8,1,6,5,4,3,2}
level:0 heap: 7
level:1 heap: 8 1
level:2 heap: 6 5 4 3
level:3 heap: 2
swap_left_child:{8,7,1,6,5,4,3,2}
level:0 heap: 8
level:1 heap: 7 1
level:2 heap: 6 5 4 3
level:3 heap: 2
put_largest_at_end:{2,7,1,6,5,4,3,8}
level:0 heap: 2
level:1 heap: 7 1
level:2 heap: 6 5 4 3
level:3 heap: 8
swap_right_child:{2,7,3,6,5,4,1}
level:0 heap: 2
level:1 heap: 7 3
level:2 heap: 6 5 4 1
swap_left_child:{2,7,4,6,5,3,1}
level:0 heap: 2
level:1 heap: 7 4
level:2 heap: 6 5 3 1
swap_right_child:{4,7,2,6,5,3,1}
level:0 heap: 4
level:1 heap: 7 2
level:2 heap: 6 5 3 1
swap_left_child:{7,4,2,6,5,3,1}
level:0 heap: 7
level:1 heap: 4 2
level:2 heap: 6 5 3 1
put_largest_at_end:{1,4,2,6,5,3,7}
level:0 heap: 1
level:1 heap: 4 2
level:2 heap: 6 5 3 7
swap_left_child:{1,4,3,6,5,2}
level:0 heap: 1
level:1 heap: 4 3
level:2 heap: 6 5 2
swap_right_child:{1,5,3,6,4,2}
level:0 heap: 1
level:1 heap: 5 3
level:2 heap: 6 4 2
swap_left_child:{1,6,3,5,4,2}
level:0 heap: 1
level:1 heap: 6 3
level:2 heap: 5 4 2
swap_right_child:{3,6,1,5,4,2}
level:0 heap: 3
level:1 heap: 6 1
level:2 heap: 5 4 2
swap_left_child:{6,3,1,5,4,2}
level:0 heap: 6
level:1 heap: 3 1
level:2 heap: 5 4 2
put_largest_at_end:{2,3,1,5,4,6}
level:0 heap: 2
level:1 heap: 3 1
level:2 heap: 5 4 6
swap_right_child:{2,4,1,5,3}
level:0 heap: 2
level:1 heap: 4 1
level:2 heap: 5 3
swap_left_child:{2,5,1,4,3}
level:0 heap: 2
level:1 heap: 5 1
level:2 heap: 4 3
swap_left_child:{5,2,1,4,3}
level:0 heap: 5
level:1 heap: 2 1
level:2 heap: 4 3
put_largest_at_end:{3,2,1,4,5}
level:0 heap: 3
level:1 heap: 2 1
level:2 heap: 4 5
swap_left_child:{3,4,1,2}
level:0 heap: 3
level:1 heap: 4 1
level:2 heap: 2
swap_left_child:{4,3,1,2}
level:0 heap: 4
level:1 heap: 3 1
level:2 heap: 2
put_largest_at_end:{2,3,1,4}
level:0 heap: 2
level:1 heap: 3 1
level:2 heap: 4
swap_left_child:{3,2,1}
level:0 heap: 3
level:1 heap: 2 1
put_largest_at_end:{1,2,3}
level:0 heap: 1
level:1 heap: 2 3
swap_left_child:{2,1}
level:0 heap: 2
level:1 heap: 1
put_largest_at_end:{1,2}
level:0 heap: 1
level:1 heap: 2
post_sort:{1,2,3,4,5,6,7,8,9}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 4 5 6 7
level:3 heap: 8 9
Case III
pre_sort:{5,5,5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
level:3 heap: 5 5
put_largest_at_end:{5,5,5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
level:3 heap: 5 5
put_largest_at_end:{5,5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
level:3 heap: 5
put_largest_at_end:{5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
put_largest_at_end:{5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5
put_largest_at_end:{5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5
put_largest_at_end:{5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5
put_largest_at_end:{5,5,5}
level:0 heap: 5
level:1 heap: 5 5
put_largest_at_end:{5,5}
level:0 heap: 5
level:1 heap: 5
post_sort:{5,5,5,5,5,5,5,5,5}
level:0 heap: 5
level:1 heap: 5 5
level:2 heap: 5 5 5 5
level:3 heap: 5 5
Case IV
pre_sort:{1,2,3,4,5,6,7,8,9}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 4 5 6 7
level:3 heap: 8 9
swap_right_child:{1,2,3,9,5,6,7,8,4}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 9 5 6 7
level:3 heap: 8 4
swap_right_child:{1,2,7,9,5,6,3,8,4}
level:0 heap: 1
level:1 heap: 2 7
level:2 heap: 9 5 6 3
level:3 heap: 8 4
swap_right_child:{1,5,7,9,2,6,3,8,4}
level:0 heap: 1
level:1 heap: 5 7
level:2 heap: 9 2 6 3
level:3 heap: 8 4
swap_left_child:{1,9,7,5,2,6,3,8,4}
level:0 heap: 1
level:1 heap: 9 7
level:2 heap: 5 2 6 3
level:3 heap: 8 4
swap_right_child:{7,9,1,5,2,6,3,8,4}
level:0 heap: 7
level:1 heap: 9 1
level:2 heap: 5 2 6 3
level:3 heap: 8 4
swap_left_child:{9,7,1,5,2,6,3,8,4}
level:0 heap: 9
level:1 heap: 7 1
level:2 heap: 5 2 6 3
level:3 heap: 8 4
put_largest_at_end:{4,7,1,5,2,6,3,8,9}
level:0 heap: 4
level:1 heap: 7 1
level:2 heap: 5 2 6 3
level:3 heap: 8 9
swap_left_child:{4,7,1,8,2,6,3,5}
level:0 heap: 4
level:1 heap: 7 1
level:2 heap: 8 2 6 3
level:3 heap: 5
swap_right_child:{4,7,3,8,2,6,1,5}
level:0 heap: 4
level:1 heap: 7 3
level:2 heap: 8 2 6 1
level:3 heap: 5
swap_left_child:{4,7,6,8,2,3,1,5}
level:0 heap: 4
level:1 heap: 7 6
level:2 heap: 8 2 3 1
level:3 heap: 5
swap_left_child:{4,8,6,7,2,3,1,5}
level:0 heap: 4
level:1 heap: 8 6
level:2 heap: 7 2 3 1
level:3 heap: 5
swap_right_child:{6,8,4,7,2,3,1,5}
level:0 heap: 6
level:1 heap: 8 4
level:2 heap: 7 2 3 1
level:3 heap: 5
swap_left_child:{8,6,4,7,2,3,1,5}
level:0 heap: 8
level:1 heap: 6 4
level:2 heap: 7 2 3 1
level:3 heap: 5
put_largest_at_end:{5,6,4,7,2,3,1,8}
level:0 heap: 5
level:1 heap: 6 4
level:2 heap: 7 2 3 1
level:3 heap: 8
swap_left_child:{5,7,4,6,2,3,1}
level:0 heap: 5
level:1 heap: 7 4
level:2 heap: 6 2 3 1
swap_left_child:{7,5,4,6,2,3,1}
level:0 heap: 7
level:1 heap: 5 4
level:2 heap: 6 2 3 1
put_largest_at_end:{1,5,4,6,2,3,7}
level:0 heap: 1
level:1 heap: 5 4
level:2 heap: 6 2 3 7
swap_left_child:{1,6,4,5,2,3}
level:0 heap: 1
level:1 heap: 6 4
level:2 heap: 5 2 3
swap_right_child:{4,6,1,5,2,3}
level:0 heap: 4
level:1 heap: 6 1
level:2 heap: 5 2 3
swap_left_child:{6,4,1,5,2,3}
level:0 heap: 6
level:1 heap: 4 1
level:2 heap: 5 2 3
put_largest_at_end:{3,4,1,5,2,6}
level:0 heap: 3
level:1 heap: 4 1
level:2 heap: 5 2 6
swap_left_child:{3,5,1,4,2}
level:0 heap: 3
level:1 heap: 5 1
level:2 heap: 4 2
swap_left_child:{5,3,1,4,2}
level:0 heap: 5
level:1 heap: 3 1
level:2 heap: 4 2
put_largest_at_end:{2,3,1,4,5}
level:0 heap: 2
level:1 heap: 3 1
level:2 heap: 4 5
swap_left_child:{2,4,1,3}
level:0 heap: 2
level:1 heap: 4 1
level:2 heap: 3
swap_left_child:{4,2,1,3}
level:0 heap: 4
level:1 heap: 2 1
level:2 heap: 3
put_largest_at_end:{3,2,1,4}
level:0 heap: 3
level:1 heap: 2 1
level:2 heap: 4
put_largest_at_end:{1,2,3}
level:0 heap: 1
level:1 heap: 2 3
swap_left_child:{2,1}
level:0 heap: 2
level:1 heap: 1
put_largest_at_end:{1,2}
level:0 heap: 1
level:1 heap: 2
post_sort:{1,2,3,4,5,6,7,8,9}
level:0 heap: 1
level:1 heap: 2 3
level:2 heap: 4 5 6 7
level:3 heap: 8 9
