package algorithm.sort;

import java.util.Random;

public class HeapSort {

public static void main(String[] args) {

int problemSize = 17;

final Random random = new Random();

int[] data = new int[]{90,38,5,55,26,76,36,11,51,2,16,64,81,1,48,9,77};

// Insert的构造方式，复杂度是O( N * LogN )

int[] maxHeap = new int[problemSize];

for(int i = 0; i < problemSize; i ++) {

insert(maxHeap, i, data[i]);

}

System.out.println(" -- Create O(N Log N) --");

printHeap(maxHeap);

System.out.println();

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

System.out.println(extract(maxHeap, i));

}

System.out.println();

System.out.println(" -- Create O(N) --");

heapify(data, problemSize);

printHeap(data);

System.out.println();

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

System.out.println(extract(data, i));

}

}

static void insert(int[] binaryHeap, int i, int value) {

// Step 1. put value at the end of binary heap

binaryHeap[i] = value;

// Step 2. keep binary heap

int end = i - 1;

if(end < 0) {

return;

}

while(i > 0 && binaryHeap[parentIndex(i)] < binaryHeap[i]){

swap(binaryHeap, parentIndex(i), i);

i = parentIndex(i);

}

}

static int extract(int[] binaryHeap, int end) {

int max = binaryHeap[0];

binaryHeap[0] = binaryHeap[end];

binaryHeap[end] = 0;

int i = 0;

while( leftChildIndex(i) <= (end - 1)) {

// Select bigger child then swap with it

int position = i;

int leftSon = leftChildIndex(i);

// First, compare with left child

if(binaryHeap[i] < binaryHeap[leftSon]) {

position = leftSon;

}

// Second, if there has right child and that child is greater

if( (leftSon + 1) <= (end -1) && binaryHeap[leftSon + 1] > binaryHeap[leftSon]) {

position = leftSon + 1;

}

// Node i holds the largest element, this means that we are done at this level

if(position == i) {

return max;

}else {

// Continue sifting down the child

swap(binaryHeap, i, position);

i = position;

}

}

return max;

}

static void heapify(int[] binarayHeap, int length) {

// 找到最后一个叶子节点的父节点，以此为起点。

int i = parentIndex(length-1);

// 每次下标减1，从而遍历整个堆，调整并保持堆的特性。

for(; i > 0; i--) {

siftDown(binarayHeap, i);

}

}

// 向下检查比较

static void siftDown(int[] binaryHeap, int index) {

int end = binaryHeap.length - 1;

while( leftChildIndex(index) <= end) {

// Select bigger child then swap with it

int position = index;

int leftSon = leftChildIndex(index);

// First, compare with left child

if(binaryHeap[index] < binaryHeap[leftSon]) {

position = leftSon;

}

// Second, if there has right child and that child is greater

if( (leftSon + 1) <= end && binaryHeap[leftSon + 1] > binaryHeap[position]) {

position = leftSon + 1;

}

// Node i holds the largest element, this means that we are done at this level

if(position == index) {

return;

}else {

// Continue sifting down the child

swap(binaryHeap, index, position);

index = position;

}

}

}

/** Help Methods **/

static int parentIndex(int n) {

return (n-1)/2;

}

static int leftChildIndex(int n) {

return 2*n + 1;

}

static int rightChildIndex(int n) {

return 2*n + 2;

}

static void swap(int[] array, int from, int to) {

int temp = array[from];

array[from] = array[to];

array[to] = temp;

}

static void printHeap(int[] heap) {

int length = heap.length;

int k = 0;

int i = 0;

// Log N Times Loop

for(; (int)Math.pow(2, i) < length; i++ ) {

System.out.print("Level " + i + " : ");

int distance = (int)Math.pow(2,i);

if((int)Math.pow(2,i + 1) > length) {

distance = length - distance + 1;

}

for(int j = 0; j < distance; j++, k++) {

System.out.print(heap[k] + " ");

}

System.out.println();

}

if(k < length) {

System.out.print("Level " + i + " : ");

for(; k < length; k++) {

System.out.print(heap[k] + " ");

}

}

}

}