package chap12;


import chap3.EmptyCollectionException;

public class ArrayHeap<T> extends ArrayBinaryTree<T> implements HeapADT<T> {
	private HeapNode<T> last,root;
	private T maxElement;

	public ArrayHeap() {
		super();
	}
	public ArrayHeap (T element) {
		root = new HeapNode<T>(element);
		last = (HeapNode<T>)root;
	}
	@Override
	public void addElement(T obj) {
		if (count == tree.length) {
			expandCapacity();
		}
		tree[count] = obj;
		count++;
		modCount++;

		if (count > 1) {
			// 检查当前的插入
			heapModifyAdd();
		}
	}

	private void heapModifyAdd() {
		T temp;
		int next = count - 1;
		temp = tree[next];
		while (next != 0
				&& (((Comparable) temp).compareTo(tree[(next - 1) / 2]) < 0)) {
			tree[next] = tree[(next - 1) / 2];
			next = (next - 1) / 2;
		}
		tree[next] = temp;
	}

	@Override
	public T removeMin() throws EmptyCollectionException {
		if (isEmpty()) {
			throw new EmptyCollectionException("ArrayHeap");
		}
		T minElement = tree[0];
		tree[0] = tree[count - 1];
		heapModifyRemove();
		count--;//当前的空白位置--
		modCount--;
		return minElement;
	}
//	@Override
//	public T removeMax() throws EmptyCollectionException
//	{
//		if (isEmpty())
//			throw new EmptyCollectionException("ArrayHeap");
//
//		T maxElement = tree[0];
//		tree[0] = tree[count-1];
//		heapifyRemove((HeapNode<T>)root);
//		count--;
//		modCount--;
//		tree[count] =null;
//
//		return maxElement;
//	}

	public void heapifyRemove(HeapNode<T> root) {
		T temp;
		HeapNode<T> current = root;
		HeapNode<T> next = largerChild (current);
		while (next != null &&
				Integer.parseInt(String.valueOf(next.element)) >Integer.parseInt(String.valueOf(current.element)) )
		{
			temp = current.element;
			current.element = next.element;
			next.element = temp;
			current = next;
			next = largerChild (current);
		}
	}
	public HeapNode<T> largerChild (HeapNode<T> node) {
		HeapNode<T> larger = null;
		if (node.left == null && node.right == null)
			larger = null;
		else
		if (node.left == null)
			larger = (HeapNode<T>)node.right;
		else
		if (node.right == null)
			larger = (HeapNode<T>)node.left;
		else
		if (Integer.parseInt (String.valueOf((HeapNode<T>)node.left))>Integer.parseInt (String.valueOf((HeapNode<T>) node.right)))
			larger = (HeapNode<T>)node.left;
		else
			larger = (HeapNode<T>)node.right;
		return larger;
	}

	/**
	 * //删除修改堆结构
	 */
	private void heapModifyRemove() {
		T temp;
		// 开始的三个结点
		int node = 0;
		int left = 1;
		int right = 2;
		
		int next;

		if ((tree[left] == null) && (tree[right] == null))
			next = count;
		else if (tree[right] == null)
			next = left;//右边为null
		else if (((Comparable) tree[left]).compareTo(tree[right]) < 0)
			next = left;
		else
			next = right;
		temp = tree[node];//临时存储  一个需要迁移的位置

		
		while ((next < count)
				&& (((Comparable) tree[next]).compareTo(temp) < 0)) {
			tree[node] = tree[next];
			node = next;
			left = 2 * node + 1;
			right = 2 * (node + 1);
			if ((tree[left] == null) && (tree[right] == null))
				next = count;
			else if (tree[right] == null)
				next = left;
			else if (((Comparable) tree[left]).compareTo(tree[right]) < 0)
				next = left;
			else
				next = right;
		}
		//最后放在node
		tree[node] = temp;

	}

	@Override
	public T findMin() {
		if (isEmpty())
			throw new EmptyCollectionException("ArrayHeap");
		return tree[0];
	}

}