java heap

import java.util.Arrays;

public class HeapTest {

public static void main(String[] args) {

int[] heap = { 1, 9, 8, 2, 11, 90, 1, 34, 32, 21, 43, 34, 56, 78, 89, 87, 69 };

int heapSize = heap.length;

System.out.println("before heap creation "+Arrays.toString(heap));

createHeap(heap,heapSize);

System.out.println("after heap creation "+Arrays.toString(heap));

heapSort(heap, heapSize);

System.out.println("after heap sort "+Arrays.toString(heap));

}

private static void createHeap(int[] heap,int heapSize) {

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

bubble_up(heap, i);

}

}

private static void heapSort(int[] heap,int heapSize) {

while (heapSize >= 1) {

extract(heap, heapSize);

--heapSize;

}

}

private static int extract(int[] arr, int len) {

if (len == 0)

return -1;

int max = arr[0];

swap(arr, 0, len - 1);

bubble_down(arr, 0, len - 2);

return max;

}

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

int tmp = a[i];

a[i] = a[j];

a[j] = tmp;

}

private static void bubble_down(int[] a, int root, int last_index) {

if (last_index <= 0)

return;

int l = 2 * root + 1;

if (l > last_index)

return;

int r = 2 * root + 2;

int new_parent = l;

if (r <= last_index && a[r] > a[l])

new_parent = r;

if (a[root] < a[new_parent]) {

swap(a, root, new_parent);

bubble_down(a, new_parent, last_index);

}

}

private static void bubble_up(int[] heap, int last_index) {

if (last_index == 0)

return;

int parent = (last_index - 1) / 2;

if (heap[last_index] > heap[parent]) {

swap(heap, last_index, parent);

bubble_up(heap, parent);

}

}

}