《Java数据结构跟算法》第二版 Robert lafore 编程作业 第十二章

《Java数据结构和算法》第二版 Robert lafore 编程作业 第十二章

《Java数据结构和算法》第二版 Robert lafore 编程作业 第十二章

/*
 	编程作业 
 	12.1 修改heap.java程序（清单12.1），使堆变为升序的，而不是降序的堆。（这
 		 就是说，根节点上的数据项是最小的，机时不是最大的。）确保所有的操作都
 		 能正确地执行。
 	12.2 用heap.java程序中的insert()方法在堆中插入一个新节点,确保不违背堆的
 		 条件。另编写toss()方法，把新节点放到堆数组中，不需要保持堆的条件。
 		 （可能每个新节点只是简单地放在数组的未端。）再编写一个restoreHeap()
 		 方法，它能在全堆恢复堆的条件。重复应用toss()，一次插入大量的数据项，
 		 然后再用一次restoreHeap()，比反复应用insert()的效率要高。查看堆排序
 		 的描述找到暗示。用insert()插入几个数据，再用toss()方法放置几个数据，
 		 然后再用restoreHeap()恢复堆，以此测试编写的程序。
 	12.3 应用堆取代数组来实现priorityQ.java程序（清单4.6）中PriorityQ类。可
 		 以不用修改heap.java程序（清单12.1）中的Heap类，直接应用它。把它作成
 		 一个降序队列（移除最大数据项）。
 	12.4 用基于数组的堆实现的优先级队列存在一个问题，就是数组的大小为固定的。
 		 如果数据量超过了数组容量，就需要扩展数组，就像在第11章的编程作业11.4
 		 中对哈希表所做的修改一样。用普通的二叉搜索树而不是堆来实现优先级队列
 		 就可以避免这个问题。一棵树可以要多在就有多大（只要不超过系统内存的容
 		 量就行）。从tree.java程序（清单8.1）中的Tree类出发，修改这个类，使
 		 它支持优先级队列，增加移除最大数据项的方法removeMax()。这一点在堆中
 		 是很容易作到的。但是在树中稍微有点困难。如何在树中找到最大的数据项呢?
 		 当移除一个节点时需要考虑它的子节点吗？编写change()方法是一种选择。用
 		 它在二叉搜索树中移除老数据项和插入另一个不同关键字的新数据项是很容易
 		 的。
 	12.5 编写程序实现本单中所讨论过的树堆（基于树而实现的堆），确保能够进行移
 	 	 除最大的数据项，插入数据项，以及修改数据项关键字的操作。
 */
package chap12;

// heap.java
// demonstrates heaps
// to run this program: C>java HeapApp
import java.io.*;

////////////////////////////////////////////////////////////////
class Node {
	private int iData;             // data item (key)

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

	public Node(int key)           // constructor
	{
		iData = key;
	}

	// -------------------------
	public int getKey() {
		return iData;
	}

	// -------------------------
	public void setKey(int id) {
		iData = id;
	}
	// -------------------------
}  // end class Node
// //////////////////////////////////////////////////////////////

class Heap {
	private Node[] heapArray;
	private int maxSize;           // size of array
	private int currentSize;       // number of nodes in array

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

	public int getCurrentSize() {
		return currentSize;
	}

	public Heap(int mx)            // constructor
	{
		maxSize = mx;
		currentSize = 0;
		heapArray = new Node[maxSize];  // create array
	}

	// -------------------------
	public boolean isEmpty() {
		return currentSize == 0;
	}

	// -------------------------
	public boolean insert(int key) {
		if (currentSize == maxSize)
			return false;
		Node newNode = new Node(key);
		heapArray[currentSize] = newNode;
		trickleUp(currentSize++);
		return true;
	}  // end insert()
		// -------------------------

	public void trickleUp(int index) {
		int parent = (index - 1) / 2;
		Node bottom = heapArray[index];

		while (index > 0 &&
		// ============================================
		// 编程作业 12.1
				heapArray[parent].getKey() > bottom.getKey())
		// ============================================
		{
			heapArray[index] = heapArray[parent];  // move it down
			index = parent;
			parent = (parent - 1) / 2;
		}  // end while
		heapArray[index] = bottom;
	}  // end trickleUp()
		// -------------------------

	public Node remove()           // delete item with max key
	{                           // (assumes non-empty list)
		Node root = heapArray[0];
		heapArray[0] = heapArray[--currentSize];
		trickleDown(0);
		return root;
	}  // end remove()
		// -------------------------

	public void trickleDown(int index) {
		int litterChild;
		Node top = heapArray[index];       // save root
		while (index < currentSize / 2)       // while node has at
		{                               // least one child,
			int leftChild = 2 * index + 1;
			int rightChild = leftChild + 1;
			// find larger child
			// ==========================================================
			// 编程作业 12.1
			if (rightChild < currentSize &&  // (rightChild exists?)
					heapArray[leftChild].getKey() > heapArray[rightChild]
							.getKey())
				litterChild = rightChild;
			else
				litterChild = leftChild;
			// top >= largerChild?
			if (top.getKey() <= heapArray[litterChild].getKey())
				break;
			// ==========================================================
			// shift child up
			heapArray[index] = heapArray[litterChild];
			index = litterChild;            // go down
		}  // end while
		heapArray[index] = top;            // root to index
	}  // end trickleDown()
		// -------------------------

	public boolean change(int index, int newValue) {
		if (index < 0 || index >= currentSize)
			return false;
		int oldValue = heapArray[index].getKey(); // remember old
		heapArray[index].setKey(newValue);  // change to new
		// =================================================
		// 编程作业 12.1
		if (oldValue > newValue)             // if raised,
			trickleUp(index);                // trickle it up
		else
			trickleDown(index);              // trickle it down
		// if lowered,
		// =================================================
		return true;
	}  // end change()

	// =================================================================
	// 编程作业 12.2
	public void toss(int key) {
		this.heapArray[currentSize++] = new Node(key);
	}

	// =================================================================
	// 编程作业 12.2
	public void restoreHeap() {
		for (int j = currentSize / 2 - 1; j >= 0; j--) {
			trickleDown(j);
		}
	}

	// =================================================================
	// 编程作业 12.3
	public Node peek() {
		return heapArray[0];
	}

	// =================================================================
	// -------------------------

	public void displayHeap() {
		System.out.print("heapArray: ");    // array format
		for (int m = 0; m < currentSize; m++)
			if (heapArray[m] != null)
				System.out.print(heapArray[m].getKey() + " ");
			else
				System.out.print("-- ");
		System.out.println();
		// heap format
		int nBlanks = 32;
		int itemsPerRow = 1;
		int column = 0;
		int j = 0;                          // current item
		String dots = "...............................";
		System.out.println(dots + dots);      // dotted top line

		while (currentSize > 0)              // for each heap item
		{
			if (column == 0)                  // first item in row?
				for (int k = 0; k < nBlanks; k++)
					// preceding blanks
					System.out.print(' ');
			// display item
			System.out.print(heapArray[j].getKey());

			if (++j == currentSize)           // done?
				break;

			if (++column == itemsPerRow)        // end of row?
			{
				nBlanks /= 2;                 // half the blanks
				itemsPerRow *= 2;             // twice the items
				column = 0;                   // start over on
				System.out.println();         // new row
			} else
				// next item on row
				for (int k = 0; k < nBlanks * 2 - 2; k++)
					System.out.print(' ');     // interim blanks
		}  // end for
		System.out.println("\n" + dots + dots); // dotted bottom line
	}  // end displayHeap()
		// -------------------------
}  // end class Heap
// //////////////////////////////////////////////////////////////

public class HeapApp {
	public static void main(String[] args) throws IOException {
		int value, value2;
		Heap theHeap = new Heap(31);  // make a Heap; max size 31
		boolean success;

		// =========================================
		// 编程作业 12.1
		theHeap.insert(70);           // insert 10 items
		theHeap.insert(40);
		theHeap.insert(50);
		theHeap.insert(20);
		theHeap.insert(60);
		theHeap.insert(100);
		theHeap.insert(80);
		theHeap.insert(30);
		theHeap.insert(10);
		theHeap.insert(90);

		// =========================================
		// 编程作业 12.2
		theHeap.toss(5);
		theHeap.toss(15);
		theHeap.toss(25);
		theHeap.toss(35);
		theHeap.toss(45);
		theHeap.restoreHeap();
		// =========================================

		while (true)                   // until [Ctrl]-[C]
		{
			System.out.print("Enter first letter of ");
			System.out.print("show, insert, remove, change: ");
			int choice = getChar();
			switch (choice) {
			case 's':                        // show
				theHeap.displayHeap();
				break;
			case 'i':                        // insert
				System.out.print("Enter value to insert: ");
				value = getInt();
				success = theHeap.insert(value);
				if (!success)
					System.out.println("Can't insert; heap full");
				break;
			case 'r':                        // remove
				if (!theHeap.isEmpty())
					theHeap.remove();
				else
					System.out.println("Can't remove; heap empty");
				break;
			case 'c':                        // change
				System.out.print("Enter current index of item: ");
				value = getInt();
				System.out.print("Enter new key: ");
				value2 = getInt();
				success = theHeap.change(value, value2);
				if (!success)
					System.out.println("Invalid index");
				break;
			default:
				System.out.println("Invalid entry\n");
			}  // end switch
		}  // end while
	}  // end main()
		// -------------------------

	public static String getString() throws IOException {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String s = br.readLine();
		return s;
	}

	// -------------------------
	public static char getChar() throws IOException {
		String s = getString();
		return s.charAt(0);
	}

	// -------------------------
	public static int getInt() throws IOException {
		String s = getString();
		return Integer.parseInt(s);
	}
	// -------------------------
}  // end class HeapApp
// //////////////////////////////////////////////////////////////

 

package chap12;

// priorityQ.java
// demonstrates priority queue
// to run this program: C>java PriorityQApp
////////////////////////////////////////////////////////////////
//==============================================================
//编程作业 12.3
class PriorityQ {
	// array in sorted order, from max at 0 to min at size-1
	private int maxSize;
	private Heap queHeap;

	// -------------------------
	public PriorityQ(int s)          // constructor
	{
		maxSize = s;
		queHeap = new Heap(maxSize);
	}

	// -------------------------
	public void insert(int item)    // insert item
	{
		queHeap.insert(item);
	}  // end insert()

	// -------------------------
	public int remove()             // remove minimum item
	{								// assumes non-empty queue
		return queHeap.remove().getKey();
	}

	// -------------------------
	public int peek()            // peek at minimum item
	{
		// assumes non-empty queue
		return queHeap.peek().getKey();
	}

	// -------------------------
	public boolean isEmpty()         // true if queue is empty
	{
		return queHeap.getCurrentSize() == 0;
	}

	// -------------------------
	public boolean isFull()          // true if queue is full
	{
		return queHeap.getCurrentSize() == maxSize;
	}

	public void display() {
		queHeap.displayHeap();
	}
	// -------------------------
}  // end class PriorityQ
// ==============================================================
// //////////////////////////////////////////////////////////////

public class PriorityQApp {
	public static void main(String[] args) {
		PriorityQ thePQ = new PriorityQ(5);
		thePQ.insert(50);
		thePQ.insert(40);
		thePQ.insert(30);
		thePQ.insert(20);
		thePQ.insert(10);
		System.out.println(thePQ.remove());
		System.out.println(thePQ.peek());
		while (!thePQ.isEmpty()) {
			System.out.print(thePQ.remove() + " ");
		}
		System.out.println();
	}  // end main()
		// -------------------------
}  // end class PriorityQApp
// //////////////////////////////////////////////////////////////

 

package chap12;

// tree.java
// demonstrates binary tree
// to run this program: C>java TreeApp
import java.io.*;
import java.util.*;               // for Stack class
////////////////////////////////////////////////////////////////

class Node1 {
	public int iData;              // data item (key)
	public Node1 leftChild;         // this node's left child
	public Node1 rightChild;        // this node's right child

	public Node1() {
	}

	public Node1(int key) {
		this.iData = key;
	}

	public void displayNode()      // display ourself
	{
		System.out.print(iData);
	}

	public int getKey() {
		return iData;
	}
}  // end class Node
// //////////////////////////////////////////////////////////////

class Tree {
	private Node1 root;             // first node of tree

	// -------------------------
	public Tree()                  // constructor
	{
		root = null;
	}            // no nodes in tree yet

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

	public Node1 find(int key)      // find node with given key
	{                           // (assumes non-empty tree)
		if (root == null) {
			return null;
		}
		Node1 current = root;               // start at root
		while (current.iData != key)        // while no match,
		{
			if (key < current.iData)         // go left?
				current = current.leftChild;
			else
				// or go right?
				current = current.rightChild;
			if (current == null)             // if no child,
				return null;                 // didn't find it
		}
		return current;                    // found it
	}  // end find()
		// -------------------------

	public void insert(int id) {
		Node1 newNode = new Node1();    // make new node
		newNode.iData = id;           // insert data
		if (root == null)                // no node in root
			root = newNode;
		else                          // root occupied
		{
			Node1 current = root;       // start at root
			Node1 parent;
			while (true)                // (exits internally)
			{
				parent = current;
				if (id < current.iData)  // go left?
				{
					current = current.leftChild;
					if (current == null)  // if end of the line,
					{                 // insert on left
						parent.leftChild = newNode;
						return;
					}
				}  // end if go left
				else                    // or go right?
				{
					current = current.rightChild;
					if (current == null)  // if end of the line
					{                 // insert on right
						parent.rightChild = newNode;
						return;
					}
				}  // end else go right
			}  // end while
		}  // end else not root
	}  // end insert()
		// -------------------------

	public boolean delete(int key) // delete node with given key
	{                           // (assumes non-empty list)
		Node1 current = root;
		Node1 parent = root;
		boolean isLeftChild = true;

		while (current.iData != key)        // search for node
		{
			parent = current;
			if (key < current.iData)         // go left?
			{
				isLeftChild = true;
				current = current.leftChild;
			} else                            // or go right?
			{
				isLeftChild = false;
				current = current.rightChild;
			}
			if (current == null)             // end of the line,
				return false;                // didn't find it
		}  // end while
			// found node to delete

		// if no children, simply delete it
		if (current.leftChild == null && current.rightChild == null) {
			if (current == root)             // if root,
				root = null;                 // tree is empty
			else if (isLeftChild)
				parent.leftChild = null;     // disconnect
			else
				// from parent
				parent.rightChild = null;
		}

		// if no right child, replace with left subtree
		else if (current.rightChild == null)
			if (current == root)
				root = current.leftChild;
			else if (isLeftChild)
				parent.leftChild = current.leftChild;
			else
				parent.rightChild = current.leftChild;

		// if no left child, replace with right subtree
		else if (current.leftChild == null)
			if (current == root)
				root = current.rightChild;
			else if (isLeftChild)
				parent.leftChild = current.rightChild;
			else
				parent.rightChild = current.rightChild;

		else  // two children, so replace with inorder successor
		{
			// get successor of node to delete (current)
			Node1 successor = getSuccessor(current);

			// connect parent of current to successor instead
			if (current == root)
				root = successor;
			else if (isLeftChild)
				parent.leftChild = successor;
			else
				parent.rightChild = successor;

			// connect successor to current's left child
			successor.leftChild = current.leftChild;
		}  // end else two children
			// (successor cannot have a left child)
		return true;                                // success
	}  // end delete()
		// -------------------------
		// returns node with next-highest value after delNode
		// goes to right child, then right child's left descendents

	private Node1 getSuccessor(Node1 delNode) {
		Node1 successorParent = delNode;
		Node1 successor = delNode;
		Node1 current = delNode.rightChild;   // go to right child
		while (current != null)               // until no more
		{                                 // left children,
			successorParent = successor;
			successor = current;
			current = current.leftChild;      // go to left child
		}
		// if successor not
		if (successor != delNode.rightChild)  // right child,
		{                                 // make connections
			successorParent.leftChild = successor.rightChild;
			successor.rightChild = delNode.rightChild;
		}
		return successor;
	}

	// -------------------------
	public void traverse(int traverseType) {
		switch (traverseType) {
		case 1:
			System.out.print("\nPreorder traversal: ");
			preOrder(root);
			break;
		case 2:
			System.out.print("\nInorder traversal:  ");
			inOrder(root);
			break;
		case 3:
			System.out.print("\nPostorder traversal: ");
			postOrder(root);
			break;
		}
		System.out.println();
	}

	// -------------------------
	private void preOrder(Node1 localRoot) {
		if (localRoot != null) {
			System.out.print(localRoot.iData + " ");
			preOrder(localRoot.leftChild);
			preOrder(localRoot.rightChild);
		}
	}

	// -------------------------
	private void inOrder(Node1 localRoot) {
		if (localRoot != null) {
			inOrder(localRoot.leftChild);
			System.out.print(localRoot.iData + " ");
			inOrder(localRoot.rightChild);
		}
	}

	// -------------------------
	private void postOrder(Node1 localRoot) {
		if (localRoot != null) {
			postOrder(localRoot.leftChild);
			postOrder(localRoot.rightChild);
			System.out.print(localRoot.iData + " ");
		}
	}

	// -------------------------
	public void displayTree() {
		inOrder(root);
		System.out.println();
	}  // end displayTree()
	
	public void displayPostOrder() {
		postOrder(root);
		System.out.println();
	}  // end displayTree()
	// -------------------------
	// =============================================================
	// 编程作业 12.4
	public Node1 removeMax() {
		Node1 grandParent = root;
		Node1 parent = root;
		Node1 current = root;
		while (current != null) {
			grandParent = parent;
			parent = current;
			current = current.rightChild;
		}
		// parent是否为根
		if (parent == root) { // 是根节点
			root = root.leftChild;
		} else { // 不是根节点
			grandParent.rightChild = parent.leftChild;
		}
		return parent;
	}

	public Node1 peekMax() {
		Node1 parent = root;
		Node1 current = root;
		while (current != null) {
			parent = current;
			current = current.rightChild;
		}
		return parent;
	}

	public boolean isEmpty() {
		return root == null;
	}
	// =============================================================
}  // end class Tree
// //////////////////////////////////////////////////////////////

 

package chap12;

// priorityQ.java
// demonstrates priority queue
// to run this program: C>java PriorityQApp
////////////////////////////////////////////////////////////////
//==================================================================
//编程作业 12.4
class TreePriorityQ {
	// array in sorted order, from max at 0 to min at size-1
	private Tree queTree;
	private int currentSize;

	// -------------------------
	public TreePriorityQ(int s)          // constructor
	{
		queTree = new Tree();
	}

	// -------------------------
	public void insert(int item)    // insert item
	{
		queTree.insert(item);
	}  // end insert()

	// -------------------------
	public int remove()             // remove maximum item
	{								// assumes non-empty queue
		return queTree.removeMax().getKey();
	}

	// -------------------------
	public int peek()            // peek at minimum item
	{
		// assumes non-empty queue
		return queTree.peekMax().getKey();
	}

	// -------------------------
	public boolean isEmpty()         // true if queue is empty
	{
		return queTree.isEmpty();
	}

	// -------------------------
	public boolean isFull()          // true if queue is full
	{
		return false;
	}
	// -------------------------
}  // end class PriorityQ
// ==================================================================
// //////////////////////////////////////////////////////////////

public class Tree_PriorityQApp {
	public static void main(String[] args) {
		TreePriorityQ thePQ = new TreePriorityQ(5);
		thePQ.insert(10);
		thePQ.insert(20);
		thePQ.insert(30);
		thePQ.insert(40);
		thePQ.insert(50);
		System.out.println(thePQ.remove());
		System.out.println(thePQ.peek());
		while (!thePQ.isEmpty()) {
			System.out.print(thePQ.remove() + " ");
		}
		System.out.println();
	}  // end main()
		// -------------------------
}  // end class PriorityQApp
// //////////////////////////////////////////////////////////////

package chap12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class TreeHeap {
	class Node {
		private int key; // data item (key)
		private Node Parent;
		private Node LeftChild;
		private Node RightChild;

		public Node() {

		}

		public Node(int key) {
			super();
			this.key = key;
		}

		public int getKey() {
			return key;
		}

		public void setKey(int key) {
			this.key = key;
		}

		public Node getParent() {
			return Parent;
		}

		public void setParent(Node parent) {
			Parent = parent;
		}

		public Node getLeftChild() {
			return LeftChild;
		}

		public void setLeftChild(Node leftChild) {
			LeftChild = leftChild;
		}

		public Node getRightChild() {
			return RightChild;
		}

		public void setRightChild(Node rightChild) {
			RightChild = rightChild;
		}

	}

	private Node root;
	private int currentSize; // number of nodes in array

	public TreeHeap() {
		currentSize = 0;
	}

	public boolean isEmpty() {
		return currentSize == 0;
	}

	public boolean insert(int key) {
		Node nullNode = findNullNode();// 找到空节点
		nullNode.key = key; // 把值设到空节点
		trickleUp(nullNode); // 空节点上移到合适的位置
		currentSize++;
		System.out.println("insert complete! heap size is :" + currentSize);
		return true;
	}

	public Node remove() {
		if (currentSize == 0) { // 如果是空Heap
			System.out.println("remove flase! heap is empty!");
			return null;
		}
		int key = root.key;// 保存原来的key
		if (currentSize == 1) { // 如果只有根节点
			currentSize--;
			root = null;
			System.out.println("remove complete! heap size is :" + currentSize);
		} else {
			// 如果是非空Heap
			Node lastNode = findLastNode();
			root.key = lastNode.key;
			trickleDown(root);
			currentSize--;
			System.out.println("remove complete! heap size is :" + currentSize);
		}
		return new Node(key);// 返回原来的Node
	}

	private void trickleDown(Node currentNode) {
		int key = currentNode.key;
		Node parent = currentNode;
		Node bigChild;
		while (parent.LeftChild != null) {
			bigChild = parent.LeftChild;
			if (parent.RightChild != null
					&& parent.RightChild.key > parent.LeftChild.key) {
				bigChild = parent.RightChild;
			}
			if (bigChild.key <= key) {
				break;
			}
			parent.key = bigChild.key;
			parent = bigChild;
		}
		parent.key = key;
	}

	private void trickleUp(Node currentNode) {
		Node parent = currentNode.Parent;
		int key = currentNode.key;
		while (currentNode != root) {
			if (parent.key >= key) {
				break;
			} else {
				currentNode.key = parent.key;
				currentNode = parent;
				parent = parent.Parent;
			}
		}
		currentNode.key = key;
	}

	// 新建一个空节点，并把空节点插入到树的最后面
	private Node findNullNode() {
		Node nullNode = new Node(); // 创建nullNode空节点
		// 如果是非空Heap
		int[] path = getPath(currentSize + 1);// 第一个空节点的编号为currentSize+1 //
												// 计算第一个空节点的路径
		Node currentNode = root;
		for (int i = 0; i < path.length; i++) {// 按路径找到第一个空节点的正确位置，把nullNode节点链接上去
			if (path[i] == 0) {
				if (currentNode.LeftChild != null) {
					currentNode = currentNode.LeftChild;
				} else {
					currentNode.LeftChild = nullNode;
					nullNode.Parent = currentNode;
					return nullNode;
				}
			} else {
				if (currentNode.RightChild != null) {
					currentNode = currentNode.RightChild;
				} else {
					currentNode.RightChild = nullNode;
					nullNode.Parent = currentNode;
					return nullNode;
				}
			}
		}
		// 如果是空Heap
		root = nullNode; // 把新空节点赋值给root
		return nullNode;
	}

	// 找到最后一个节点，并断开与heap的连接
	private Node findLastNode() {
		Node parentNode = root;
		Node lastNode = root;

		int[] path = getPath(currentSize);// 最后一个节点的编号为currentSize //
											// 计算最后一个节点的路径
		for (int i = 0; i < path.length; i++) {
			if (path[i] == 0) { // 向左
				parentNode = lastNode;
				lastNode = lastNode.LeftChild;
				if (i == path.length - 1) { // 找到最后一个节点，断开节点和Heap的连接
					parentNode.LeftChild = null;
					lastNode.Parent = null;
					return lastNode;
				}
			} else { // 向右
				parentNode = lastNode;
				lastNode = lastNode.RightChild;
				if (i == path.length - 1) {// 找到最后一个节点，断开节点和Heap的连接
					parentNode.RightChild = null;
					lastNode.Parent = null;
					return lastNode;
				}
			}
		}
		// 如果只有一个根节点
		root = null;// 断开根节点
		return lastNode;
	}

	// 计算完全二叉树给定节点的路径,路径保有存在数组path中
	// 遍历数组path即得到即点的路径
	private int[] getPath(int NodeNumber) {
		if (NodeNumber == 0) {
			return null;
		}
		// ============================================
		// 完求二叉树求给定节点路径
		// 根据节点编号NodeNumber
		// 求得编号NodeNumber的二进制数
		// 去掉二进制的第一位,即得节点的路径
		int level = (int) (Math.log(NodeNumber) / Math.log(2)) + 1;// 节点所在的层=以2为底NodeNumber的对数
		int[] binary = new int[level];// 用来存放二进制数
		while (NodeNumber >= 1) {
			binary[--level] = NodeNumber % 2;
			NodeNumber = NodeNumber / 2;
		}
		int[] path = new int[binary.length - 1];
		System.arraycopy(binary, 1, path, 0, path.length);
		return path;
	}

	public void displayHeap() {

		if (root == null) { // 如果是空Heap
			System.out.println("heapArray: empty heap!");
			return;
		}
		// 如果非空Heap
		System.out.print("heapArray: "); // array format
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(root);
		while (!queue.isEmpty()) {
			Node node = queue.remove();
			System.out.print(node.key + " ");
			if (node.LeftChild != null) {
				queue.add(node.LeftChild);
			}
			if (node.RightChild != null) {
				queue.add(node.RightChild);
			}
		}
		System.out.println();
		int nBlanks = 32;
		int itemsPerRow = 1;
		int column = 0;
		int j = 0; // current item
		String dots = "...............................";
		System.out.println(dots + dots); // dotted top line
		queue.add(root);
		while (!queue.isEmpty()) {
			if (column == 0) // first item in row?
				for (int k = 0; k < nBlanks; k++)
					System.out.print(' ');// preceding blanks
			Node node = queue.remove();
			System.out.print(node.key);
			if (node.LeftChild != null) {
				queue.add(node.LeftChild);
			}
			if (node.RightChild != null) {
				queue.add(node.RightChild);
			}
			if (queue.isEmpty()) // done?
				break;
			if (++column == itemsPerRow) // end of row?
			{
				nBlanks /= 2; // half the blanks
				itemsPerRow *= 2; // twice the items
				column = 0; // start over on
				System.out.println(); // new row
			} else
				// next item on row
				for (int k = 0; k < nBlanks * 2 - 2; k++)
					System.out.print(' '); // interim blanks
		} // end for
		System.out.println("\n" + dots + dots); // dotted bottom line
	}

	public static void main(String[] args) throws Exception {

		int value;
		TreeHeap theHeap = new TreeHeap(); // make a TreeHeap;
		boolean success;
		theHeap.insert(70);
		theHeap.insert(40);
		theHeap.insert(50);
		theHeap.insert(20);
		theHeap.insert(60);
		theHeap.insert(100);
		theHeap.insert(80);
		theHeap.insert(30);
		theHeap.insert(10);
		theHeap.insert(90);
		boolean b = true;
		while (b) // until [Ctrl]-[C]
		{
			System.out.print("Enter first letter of ");
			System.out.print("show, insert, remove, quit: ");
			int choice = getChar();
			switch (choice) {
			case 's': // show
				theHeap.displayHeap();
				break;
			case 'i': // insert
				System.out.print("Enter value to insert: ");
				value = getInt();
				success = theHeap.insert(value);
				if (!success)
					System.out.println("Can't insert; heap full");
				break;
			case 'r': // remove
				if (!theHeap.isEmpty())
					theHeap.remove();
				else
					System.out.println("Can't remove; heap empty");
				break;
			case 'q':
				b = false;
				System.out.println("quit!byebye!");
				break;
			default:
				System.out.println("Invalid entry\n");
			} // end switch
		}// end while
	}// end main

	// -------------------------
	public static String getString() throws IOException {
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		String s = br.readLine();
		return s;
	}

	// -------------------------
	public static char getChar() throws IOException {
		String s = getString();
		return s.charAt(0);
	}

	// -------------------------
	public static int getInt() throws IOException {
		String s = getString();
		return Integer.parseInt(s);
	}
	// -------------------------
}