heap sort

import java.util.Random;

public class HeapSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		HeapSort hs = new HeapSort();
		int[] b = { 4, 7, 10, 564, 1, 8, 1, 1, 9, 4, 1, 46, 2, 96 };

		int[] c = new int[10000000];//out of memory .......
		Random r = new Random();
		for (int i = 0; i < c.length; i++) {
			c[i] = r.nextInt(10000000);
		}
		BTree tree = new BTree();
		long start = System.currentTimeMillis();
		tree.sort(c);
		long end = System.currentTimeMillis();
		System.out.println("HeapSort a array with lenght of " + c.length
				+ " in " + (end - start) + " millisecond");
	}

	private static class BTree {
		private static class Node {
			public int leftChild;
			public int rightChild;
			public int data;

			public Node(int newData) {
				leftChild = -1;
				rightChild = -1;
				data = newData;
			}
		}

		private Node[] buildTree(int[] array) {

			Node[] nodeList = new Node[array.length];
			for (int i = 0; i < array.length; i++) {
				Node node = new Node(array[i]);
				nodeList[i] = node;
			}

			for (int i = 0; i < nodeList.length; i++) {
				Node node = nodeList[i];
				if ((2 * i + 1) > nodeList.length - 1) {
					break;
				} else {
					node.leftChild = 2 * i + 1;
				}
				if ((2 * i + 2) > nodeList.length - 1) {
					break;
				} else {
					node.rightChild = 2 * i + 2;
				}
			}
			return nodeList;
		}

		private void buildmaxHeap(Node[] bTree, int toBeSored) {
			for (int i = bTree.length / 2; i >= 0; i--) {
				maxHeap(bTree, i, toBeSored);
			}
		}

		private int[] sort(int[] array) {
			Node[] bTree = buildTree(array);
			int toBeSored = array.length;
			buildmaxHeap(bTree, toBeSored);
			for (int i = toBeSored; i >= 2; i--) {
				exchangeValue(bTree[0], bTree[toBeSored - 1]);
				toBeSored--;
				maxHeap(bTree, 0, toBeSored);
			}
			int[] sortedArray = new int[array.length];
			for (int i = 0; i < bTree.length; i++) {
				sortedArray[i] = bTree[i].data;
			}
			return sortedArray;

		}

		private void maxHeap(Node[] btree, int index, int toBeSored) {

			BTree.Node node = btree[index];
			BTree.Node lNode = null;
			BTree.Node rNode = null;
			int largest = index;
			int lChild = node.leftChild;
			if (lChild != -1) {
				lNode = btree[lChild];
			}
			int rChild = node.rightChild;
			if (rChild != -1) {
				rNode = btree[rChild];
			}

			if (lChild != -1 && lChild < toBeSored
					&& lNode.data > btree[largest].data) {
				largest = lChild;

			}
			if (rChild != -1 && rChild < toBeSored
					&& rNode.data > btree[largest].data) {
				largest = rChild;
			}
			if (index != largest) {
				exchangeValue(btree[largest], node);
				maxHeap(btree, largest, toBeSored);
			}
		}

		private void exchangeValue(BTree.Node a, BTree.Node b) {
			int temp = a.data;
			a.data = b.data;
			b.data = temp;
		}
	}

}