《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 HeapAppimport 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 arrayprivate 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.1heapArray[parent].getKey() > bottom.getKey())// ============================================{heapArray[index] = heapArray[parent]; // move it downindex = parent;parent = (parent - 1) / 2;} // end whileheapArray[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 rootwhile (index < currentSize / 2) // while node has at{ // least one child,int leftChild = 2 * index + 1;int rightChild = leftChild + 1;// find larger child// ==========================================================// 编程作业 12.1if (rightChild < currentSize && // (rightChild exists?)heapArray[leftChild].getKey() > heapArray[rightChild].getKey())litterChild = rightChild;elselitterChild = leftChild;// top >= largerChild?if (top.getKey() <= heapArray[litterChild].getKey())break;// ==========================================================// shift child upheapArray[index] = heapArray[litterChild];index = litterChild; // go down} // end whileheapArray[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 oldheapArray[index].setKey(newValue); // change to new// =================================================// 编程作业 12.1if (oldValue > newValue) // if raised,trickleUp(index); // trickle it upelsetrickleDown(index); // trickle it down// if lowered,// =================================================return true;} // end change()// =================================================================// 编程作业 12.2public void toss(int key) {this.heapArray[currentSize++] = new Node(key);}// =================================================================// 编程作业 12.2public void restoreHeap() {for (int j = currentSize / 2 - 1; j >= 0; j--) {trickleDown(j);}}// =================================================================// 编程作业 12.3public Node peek() {return heapArray[0];}// =================================================================// -------------------------public void displayHeap() {System.out.print("heapArray: "); // array formatfor (int m = 0; m < currentSize; m++)if (heapArray[m] != null)System.out.print(heapArray[m].getKey() + " ");elseSystem.out.print("-- ");System.out.println();// heap formatint nBlanks = 32;int itemsPerRow = 1;int column = 0;int j = 0; // current itemString dots = "...............................";System.out.println(dots + dots); // dotted top linewhile (currentSize > 0) // for each heap item{if (column == 0) // first item in row?for (int k = 0; k < nBlanks; k++)// preceding blanksSystem.out.print(' ');// display itemSystem.out.print(heapArray[j].getKey());if (++j == currentSize) // done?break;if (++column == itemsPerRow) // end of row?{nBlanks /= 2; // half the blanksitemsPerRow *= 2; // twice the itemscolumn = 0; // start over onSystem.out.println(); // new row} else// next item on rowfor (int k = 0; k < nBlanks * 2 - 2; k++)System.out.print(' '); // interim blanks} // end forSystem.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 31boolean success;// =========================================// 编程作业 12.1theHeap.insert(70); // insert 10 itemstheHeap.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.2theHeap.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': // showtheHeap.displayHeap();break;case 'i': // insertSystem.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': // removeif (!theHeap.isEmpty())theHeap.remove();elseSystem.out.println("Can't remove; heap empty");break;case 'c': // changeSystem.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.3class PriorityQ {// array in sorted order, from max at 0 to min at size-1private 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 queuereturn queHeap.remove().getKey();}// -------------------------public int peek() // peek at minimum item{// assumes non-empty queuereturn 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 TreeAppimport java.io.*;import java.util.*; // for Stack class////////////////////////////////////////////////////////////////class Node1 {public int iData; // data item (key)public Node1 leftChild; // this node's left childpublic Node1 rightChild; // this node's right childpublic 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 rootwhile (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 nodenewNode.iData = id; // insert dataif (root == null) // no node in rootroot = newNode;else // root occupied{Node1 current = root; // start at rootNode1 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 leftparent.leftChild = newNode;return;}} // end if go leftelse // or go right?{current = current.rightChild;if (current == null) // if end of the line{ // insert on rightparent.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 itif (current.leftChild == null && current.rightChild == null) {if (current == root) // if root,root = null; // tree is emptyelse if (isLeftChild)parent.leftChild = null; // disconnectelse// from parentparent.rightChild = null;}// if no right child, replace with left subtreeelse if (current.rightChild == null)if (current == root)root = current.leftChild;else if (isLeftChild)parent.leftChild = current.leftChild;elseparent.rightChild = current.leftChild;// if no left child, replace with right subtreeelse if (current.leftChild == null)if (current == root)root = current.rightChild;else if (isLeftChild)parent.leftChild = current.rightChild;elseparent.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 insteadif (current == root)root = successor;else if (isLeftChild)parent.leftChild = successor;elseparent.rightChild = successor;// connect successor to current's left childsuccessor.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 descendentsprivate Node1 getSuccessor(Node1 delNode) {Node1 successorParent = delNode;Node1 successor = delNode;Node1 current = delNode.rightChild; // go to right childwhile (current != null) // until no more{ // left children,successorParent = successor;successor = current;current = current.leftChild; // go to left child}// if successor notif (successor != delNode.rightChild) // right child,{ // make connectionssuccessorParent.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.4public 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.4class TreePriorityQ {// array in sorted order, from max at 0 to min at size-1private 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 queuereturn queTree.removeMax().getKey();}// -------------------------public int peek() // peek at minimum item{// assumes non-empty queuereturn 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 arraypublic 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) { // 如果是空HeapSystem.out.println("remove flase! heap is empty!");return null;}int key = root.key;// 保存原来的keyif (currentSize == 1) { // 如果只有根节点currentSize--;root = null;System.out.println("remove complete! heap size is :" + currentSize);} else {// 如果是非空HeapNode 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空节点// 如果是非空Heapint[] 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;}}}// 如果是空Heaproot = nullNode; // 把新空节点赋值给rootreturn 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) { // 如果是空HeapSystem.out.println("heapArray: empty heap!");return;}// 如果非空HeapSystem.out.print("heapArray: "); // array formatQueue<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 itemString dots = "...............................";System.out.println(dots + dots); // dotted top linequeue.add(root);while (!queue.isEmpty()) {if (column == 0) // first item in row?for (int k = 0; k < nBlanks; k++)System.out.print(' ');// preceding blanksNode 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 blanksitemsPerRow *= 2; // twice the itemscolumn = 0; // start over onSystem.out.println(); // new row} else// next item on rowfor (int k = 0; k < nBlanks * 2 - 2; k++)System.out.print(' '); // interim blanks} // end forSystem.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': // showtheHeap.displayHeap();break;case 'i': // insertSystem.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': // removeif (!theHeap.isEmpty())theHeap.remove();elseSystem.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);}// -------------------------}