/**

* Implementation of heapsort

* @author William Fiset, william.alexandre.fiset@gmail.com

**/

import java.util.*;

public class Heapsort {

public static void heapsort(int[] ar) {

if (ar == null) return;

int n = ar.length;

// Heapify, converts array into binary heap, O(n)

for (int i = Math.max(0,(n/2)-1); i >= 0; i--)

sink(ar, n, i);

// Sorting bit

for(int i = n-1; i >= 0; i--) {

swap(ar, 0, i);

sink(ar, i, 0);

}

}

private static void sink(int[] ar, int n, int i) {

while (true) {

int left = 2 * i + 1; // Left node

int right = 2 * i + 2; // Right node

int largest = i;

// Right child is larger than parent

if (right < n && ar[right] > ar[largest])

largest = right;

// Left child is larger than parent

if (left < n && ar[left] > ar[largest])

largest = left;

// Move down the tree following the largest node

if (largest != i) {

swap(ar, largest, i);

i = largest;

} else break;

}

}

private static void swap(int[] ar, int i, int j) {

int tmp = ar[i];

ar[i] = ar[j];

ar[j] = tmp;

}

/* TESTING */

public static void main(String[] args) {

int[] array = {10, 4, 6, 4, 8, -13, 2, 3};

heapsort(array);

System.out.println(java.util.Arrays.toString(array));

runTests();

}

static Random RANDOM = new Random();

public static void runTests() {

final int NUM_TESTS = 1000;

for(int i = 1; i <= NUM_TESTS; i++) {

int[] array = new int[i];

// for(int j = 0; j < i; j++) array[j] = randInt(-1000000, +1000000);

for(int j = 0; j < i; j++) array[j] = randInt(-10, +10);

int[] arrayCopy = array.clone();

heapsort(array);

java.util.Arrays.sort(arrayCopy);

if (!java.util.Arrays.equals(array, arrayCopy)) {

System.out.println(Arrays.toString(array));

System.out.println("ERROR");

break;

}

}

}

static int randInt(int min, int max) {

return RANDOM.nextInt((max - min) + 1) + min;

}

}