//=================================================

// File Name       :	Heap_demo

//------------------------------------------------------------------------------

// Author          :	Common

//类名：Node_Heap

//属性：

//方法：

class Node_Heap{

	public int iData;

	public Node_Heap(int iData) {	//构造函数

		super();

		this.iData = iData;

	}

	public int getiData() {

		return iData;

	}

	public void setiData(int iData) {

		this.iData = iData;

	}

}

//类名：Heap

//属性：

//方法：

class Heap{

	private Node_Heap[] heapArray;

	public int maxSize;

	private int currentSize;

	public Heap(int maxSize) {	//构造函数

		super();

		this.maxSize = maxSize;

		this.currentSize = 0;

		heapArray = new Node_Heap[maxSize];

	}

	public boolean isEmpty(){

		return currentSize ==0;

	}

	public boolean insert(int key){

		if(currentSize == maxSize){

			return false;

		}

		Node_Heap newNode = new Node_Heap(key);

		heapArray[currentSize] = newNode;				//把插入的节点放在最后的位置

		trickleUp(currentSize++);									//插入节点并把currentSize加1

		return true;

	}

	//用于插入，把父类节点下移，然后把插入的节点放到合适的位置

	public void trickleUp(int index){

		int parent = (index-1)/2;

		Node_Heap bottom = heapArray[index];		//暂存新插入的节点，因为需要把父节点下移

		while(index>0 && heapArray[parent].getiData()<bottom.getiData()){	//如果小，就下移

			heapArray[index] = heapArray[parent];		//把父类节点下移

			index = parent;						//用于递归

			parent = (parent-1)/2;

		}

		heapArray[index] = bottom;	//把插入的节点放到合适的位置

	}

	public Node_Heap remove(){	//删除最大的节点

		Node_Heap root = heapArray[0];

		heapArray[0]=heapArray[--currentSize];

		trickleDown(0);

		return root;

	}

	//用于删除，把子类节点上移

	public void trickleDown(int index){

		int largerChild;

		Node_Heap top = heapArray[index];		//

		while(index<currentSize/2){	//如果小，就下移

			int leftChild = 2*index+1;

			int rightChild = leftChild+1;

			if(rightChild<currentSize && heapArray[leftChild].getiData() < heapArray[rightChild].getiData())

				largerChild = rightChild;

			else

				largerChild = leftChild;

			if(top.getiData()>=heapArray[largerChild].getiData())

				break;

			heapArray[index] = heapArray[largerChild];

			index = largerChild;

		}

		heapArray[index] = top;

	}

	public void displayHeap(){

		System.out.print("heapArray:");

		for(int i=0;i<heapArray.length;i++){

			if(heapArray[i] != null)

				System.out.print(heapArray[i].getiData()+" ");

			else

				System.out.print(" -- ");

		}

		System.out.println();

		int nBlanks = 32;			//定义空格

		int itemsPerRow = 1;

		int column = 0;

		int j=0;								//标记当前的数组下标，从0开始

		System.out.println("......................................................");

		while(currentSize > 0){

			if(column == 0){

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

					System.out.print(" ");

				}

			}

			System.out.print(heapArray[j].getiData());

			if(++j == currentSize){

				break;

			}

			if(++column==itemsPerRow){		//如果每一行计数等于这一行的上限，则换行

				nBlanks /= 2;				//空格数减半

				itemsPerRow *= 2;		//每一行的上限

				column = 0;

				System.out.println();

			}else{

				for(int i=0;i<nBlanks*2-2;i++){

					System.out.print(" ");

				}

			}

		}

		System.out.println("\n"+"......................................................");

	}

}

//主类

//Function        : 	Heap_demo

public class Heap_demo {

	public static void main(String[] args) {

		// TODO 自动生成的方法存根

		int anArrays[]={1,2,3,4,5,6,7,8,9,10};

		Heap theHeap = new Heap(31);

//		theHeap.insert(1);

//		theHeap.insert(2);

//		theHeap.insert(3);

//		theHeap.insert(4);

//		theHeap.insert(5);

//		theHeap.insert(6);

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

			theHeap.insert(anArrays[i]);

		}

		theHeap.displayHeap();

		//theHeap.remove();

		//theHeap.displayHeap();

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

			anArrays[i]=theHeap.remove().iData;

		}

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

			System.out.print(anArrays[i]+" ");

		}

	}

}