参考书籍《Java数据结构与算法》 第12章 堆
1.堆的引入
优先级队列 和 堆
2.堆的特点
①堆是完全二叉树
②堆一般用数组来保存
③堆中的每个节点都满足一定的条件，也就是当前节点的关键值必须大于等于（或者小于等于）它的子节点的关键值
3.堆的操作（以最大堆为例）
（1）移除最大的节点
从堆中删除节点的过程：删除的一定是堆的根节点，删除之后将堆数组的最后一个元素bottom放在根节点的位置，
然后比较bottom和它的孩子中key值较大的那个child，如果那个孩子的key值更大，那么就交换bottom和child节点的位置，
同理，按照上面的步骤继续比较，直到bottom处在满足堆条件的位置上。
这里有一个向下筛选的选择问题：
（2）插入节点
向堆中插入元素的过程：将要插入的元素newNode放在堆数组的末尾，然后将newNode的key和它的父节点parent的key比较，
如果子节点的key值更大，那么就交换newNode和parent的位置，然后按照上面的步骤继续向上比较，直到newNode找到了
一个合适的位置，即parent比它大，但是child比它小。
向上筛选则要简单了：
4.堆的优化：不是真的交换
5.编码实现
节点类Node
package ex3;
//数据结构：堆中的节点元素
public class Node {
private int key;
public Node() {
}
public Node(int key) {
this.key = key;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
}
//数据结构：堆中的节点元素
public class Node {
private int key;
public Node() {
}
public Node(int key) {
this.key = key;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
}
最小堆类MinHeap（没有优化的版本）
/**
* @Author：胡家威
* @Description：实现最小堆以及插入和删除节点
*/
package ex3;
//数据结构：堆
public class MinHeap {
private Node[] nodeArray;//用数组保存堆
private int maxsize;//堆的最大容量
private int currentsize;//当前的大小
public MinHeap(int maxsize) {
this.maxsize = maxsize;
this.currentsize = 0;
this.nodeArray = new Node[maxsize];
}
//插入节点
public void insert(Node newNode){
if(currentsize==maxsize){//堆已经满了，不能再插入节点了
System.out.println("The heap is full");
return;
}
nodeArray[currentsize] = newNode;//将要插入的节点至于节点数组的末尾
int index = currentsize;
int parent = (index-1)/2;//父节点的下标,当index=0时，parent=0！
currentsize++;//当前的节点数增加 1
while(parent>=0){//存在父节点
if(nodeArray[parent].getKey()>nodeArray[index].getKey()){//如果父节点的值大于子节点
nodeArray[index] = nodeArray[parent];//父节点往下移动
nodeArray[parent]=newNode;//子节点往上移
index = parent;//修改index和parent的值
parent = (index-1)/2;
}else {
break;//当index=0时，parent=0！要保证这种情况下也是能够跳出循环的
}
}//循环退出的条件：到达了根节点或者父节点的值更小
nodeArray[index] = newNode;//将要插入的节点赋值到最终确定的位置上
}
//删除节点，删除的节点都是根节点（key值最小的）
public void remove() {
if(currentsize==0){
System.out.println("The heap is empty");
}
Node bottom = nodeArray[currentsize-1];
nodeArray[0]=nodeArray[currentsize-1];//将最后一个节点放在根节点上
currentsize--;//当前的节点数减少1
int index = 0;
while(index<currentsize/2){//index超过了currentsize/2的话就没有孩子
int leftChild = index*2+1;//得到左右孩子，并比较得到较大的那个孩子
int rightChild = leftChild+1;
int smallerChild = leftChild;
//存在右孩子,并且右孩子的值小于左孩子的值
if(rightChild<currentsize && nodeArray[rightChild].getKey()<nodeArray[leftChild].getKey()){
smallerChild = rightChild;
}
//如果父节点的值大于孩子节点中较小的那个
if(nodeArray[index].getKey()>nodeArray[smallerChild].getKey()){
nodeArray[index]=nodeArray[smallerChild];//较小的孩子节点上移成为父节点
nodeArray[smallerChild]=bottom;//父节点往下移
index = smallerChild;//修改index的值
}
}
}
//输出堆中的数据
public void displayHeap(){
for(int i=0;i<currentsize;i++){
System.out.print(nodeArray[i].getKey()+"\t");
}
System.out.println();
}
}
* @Author：胡家威
* @Description：实现最小堆以及插入和删除节点
*/
package ex3;
//数据结构：堆
public class MinHeap {
private Node[] nodeArray;//用数组保存堆
private int maxsize;//堆的最大容量
private int currentsize;//当前的大小
public MinHeap(int maxsize) {
this.maxsize = maxsize;
this.currentsize = 0;
this.nodeArray = new Node[maxsize];
}
//插入节点
public void insert(Node newNode){
if(currentsize==maxsize){//堆已经满了，不能再插入节点了
System.out.println("The heap is full");
return;
}
nodeArray[currentsize] = newNode;//将要插入的节点至于节点数组的末尾
int index = currentsize;
int parent = (index-1)/2;//父节点的下标,当index=0时，parent=0！
currentsize++;//当前的节点数增加 1
while(parent>=0){//存在父节点
if(nodeArray[parent].getKey()>nodeArray[index].getKey()){//如果父节点的值大于子节点
nodeArray[index] = nodeArray[parent];//父节点往下移动
nodeArray[parent]=newNode;//子节点往上移
index = parent;//修改index和parent的值
parent = (index-1)/2;
}else {
break;//当index=0时，parent=0！要保证这种情况下也是能够跳出循环的
}
}//循环退出的条件：到达了根节点或者父节点的值更小
nodeArray[index] = newNode;//将要插入的节点赋值到最终确定的位置上
}
//删除节点，删除的节点都是根节点（key值最小的）
public void remove() {
if(currentsize==0){
System.out.println("The heap is empty");
}
Node bottom = nodeArray[currentsize-1];
nodeArray[0]=nodeArray[currentsize-1];//将最后一个节点放在根节点上
currentsize--;//当前的节点数减少1
int index = 0;
while(index<currentsize/2){//index超过了currentsize/2的话就没有孩子
int leftChild = index*2+1;//得到左右孩子，并比较得到较大的那个孩子
int rightChild = leftChild+1;
int smallerChild = leftChild;
//存在右孩子,并且右孩子的值小于左孩子的值
if(rightChild<currentsize && nodeArray[rightChild].getKey()<nodeArray[leftChild].getKey()){
smallerChild = rightChild;
}
//如果父节点的值大于孩子节点中较小的那个
if(nodeArray[index].getKey()>nodeArray[smallerChild].getKey()){
nodeArray[index]=nodeArray[smallerChild];//较小的孩子节点上移成为父节点
nodeArray[smallerChild]=bottom;//父节点往下移
index = smallerChild;//修改index的值
}
}
}
//输出堆中的数据
public void displayHeap(){
for(int i=0;i<currentsize;i++){
System.out.print(nodeArray[i].getKey()+"\t");
}
System.out.println();
}
}
改进版本的最小堆：
/**
* @Author：胡家威
* @Description：实现最小堆以及插入和删除节点的改进版本
*/
package ex3;
//数据结构：堆
public class MinHeapImprove {
private Node[] nodeArray;// 用数组保存堆
private int maxsize;// 堆的最大容量
private int currentsize;// 当前的大小
public MinHeapImprove(int maxsize) {
this.maxsize = maxsize;
this.currentsize = 0;
this.nodeArray = new Node[maxsize];
}
// 插入节点
public void insert(Node newNode) {
if (currentsize == maxsize) {// 堆已经满了，不能再插入节点了
System.out.println("The heap is full");
return;
}
nodeArray[currentsize] = newNode;// 将要插入的节点至于节点数组的末尾
int index = currentsize;
int parent = (index - 1) / 2;// 父节点的下标,当index=0时，parent=0！
currentsize++;// 当前的节点数增加 1
while (index > 0 // 存在父节点
&& nodeArray[parent].getKey() > newNode.getKey()) {// 如果父节点的值大于子节点
nodeArray[index] = nodeArray[parent];// 父节点往下移动
index = parent;// 修改index和parent的值
parent = (index - 1) / 2;
}// 循环退出的条件：到达了根节点或者父节点的值更小
nodeArray[index] = newNode;// 将要插入的节点赋值到最终确定的位置上
}
// 删除节点，删除的节点都是根节点（key值最小的）
public void remove() {
if (currentsize == 0) {
System.out.println("The heap is empty");
return;
}
nodeArray[0] = nodeArray[currentsize - 1];// 将最后一个节点放在根节点上
Node bottom = nodeArray[0];//保存根节点
currentsize--;// 当前的节点数减少1
int index = 0;
while (index < currentsize / 2) {// index超过了currentsize/2的话就没有孩子
int leftChild = index * 2 + 1;// 得到左右孩子，并比较得到较小的那个孩子
int rightChild = leftChild + 1;
int smallerChild = leftChild;
// 存在右孩子,并且右孩子的值小于左孩子的值
if (rightChild < currentsize && nodeArray[rightChild].getKey() < nodeArray[leftChild].getKey()) {
smallerChild = rightChild;
}
// 如果父节点的值大于孩子节点中较小的那个
if (nodeArray[index].getKey() > bottom.getKey()) {
nodeArray[index] = nodeArray[smallerChild];// 较小的孩子节点上移成为父节点
index = smallerChild;// 修改index的值
}else{
break;
}
}
nodeArray[index]=bottom;
}
// 输出堆中的数据
public void displayHeap() {
for (int i = 0; i < currentsize; i++) {
System.out.print(nodeArray[i].getKey() + "\t");
}
System.out.println();
}
}
* @Author：胡家威
* @Description：实现最小堆以及插入和删除节点的改进版本
*/
package ex3;
//数据结构：堆
public class MinHeapImprove {
private Node[] nodeArray;// 用数组保存堆
private int maxsize;// 堆的最大容量
private int currentsize;// 当前的大小
public MinHeapImprove(int maxsize) {
this.maxsize = maxsize;
this.currentsize = 0;
this.nodeArray = new Node[maxsize];
}
// 插入节点
public void insert(Node newNode) {
if (currentsize == maxsize) {// 堆已经满了，不能再插入节点了
System.out.println("The heap is full");
return;
}
nodeArray[currentsize] = newNode;// 将要插入的节点至于节点数组的末尾
int index = currentsize;
int parent = (index - 1) / 2;// 父节点的下标,当index=0时，parent=0！
currentsize++;// 当前的节点数增加 1
while (index > 0 // 存在父节点
&& nodeArray[parent].getKey() > newNode.getKey()) {// 如果父节点的值大于子节点
nodeArray[index] = nodeArray[parent];// 父节点往下移动
index = parent;// 修改index和parent的值
parent = (index - 1) / 2;
}// 循环退出的条件：到达了根节点或者父节点的值更小
nodeArray[index] = newNode;// 将要插入的节点赋值到最终确定的位置上
}
// 删除节点，删除的节点都是根节点（key值最小的）
public void remove() {
if (currentsize == 0) {
System.out.println("The heap is empty");
return;
}
nodeArray[0] = nodeArray[currentsize - 1];// 将最后一个节点放在根节点上
Node bottom = nodeArray[0];//保存根节点
currentsize--;// 当前的节点数减少1
int index = 0;
while (index < currentsize / 2) {// index超过了currentsize/2的话就没有孩子
int leftChild = index * 2 + 1;// 得到左右孩子，并比较得到较小的那个孩子
int rightChild = leftChild + 1;
int smallerChild = leftChild;
// 存在右孩子,并且右孩子的值小于左孩子的值
if (rightChild < currentsize && nodeArray[rightChild].getKey() < nodeArray[leftChild].getKey()) {
smallerChild = rightChild;
}
// 如果父节点的值大于孩子节点中较小的那个
if (nodeArray[index].getKey() > bottom.getKey()) {
nodeArray[index] = nodeArray[smallerChild];// 较小的孩子节点上移成为父节点
index = smallerChild;// 修改index的值
}else{
break;
}
}
nodeArray[index]=bottom;
}
// 输出堆中的数据
public void displayHeap() {
for (int i = 0; i < currentsize; i++) {
System.out.print(nodeArray[i].getKey() + "\t");
}
System.out.println();
}
}
注意区别：
对比插入节点的操作
没有改进前的判断条件和满足条件时的执行代码
改进之后：
测试代码：
/**
* @Author：胡家威
* @CreateTime：2011-11-9 下午12:34:21
* @Description：堆排序的样例
*/
package ex3;
public class HeapSample {
public static void main(String[] args) {
System.out.println("new heap");
// MinHeap heap = new MinHeap(20);
MinHeapImprove heap = new MinHeapImprove(20);
System.out.println("insert item");
heap.insert(new Node(10));
heap.insert(new Node(30));
heap.insert(new Node(20));
heap.insert(new Node(15));
heap.insert(new Node(40));
heap.insert(new Node(5));
heap.displayHeap();
System.out.println("remove root");
heap.remove();
heap.displayHeap();
}
}
* @Author：胡家威
* @CreateTime：2011-11-9 下午12:34:21
* @Description：堆排序的样例
*/
package ex3;
public class HeapSample {
public static void main(String[] args) {
System.out.println("new heap");
// MinHeap heap = new MinHeap(20);
MinHeapImprove heap = new MinHeapImprove(20);
System.out.println("insert item");
heap.insert(new Node(10));
heap.insert(new Node(30));
heap.insert(new Node(20));
heap.insert(new Node(15));
heap.insert(new Node(40));
heap.insert(new Node(5));
heap.displayHeap();
System.out.println("remove root");
heap.remove();
heap.displayHeap();
}
}
结果都是一样的：
原书代码：
heap.java
package chap12;
// heap.java
// demonstrates heaps
// to run this program: C>java HeapApp
////////////////////////////////////////////////////////////////
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 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 && 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 largerChild;
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
if (rightChild < currentSize && // (rightChild exists?)
heapArray[leftChild].getKey() < heapArray[rightChild].getKey())
largerChild = rightChild;
else
largerChild = leftChild;
// top >= largerChild?
if (top.getKey() >= heapArray[largerChild].getKey())
break;
// shift child up
heapArray[index] = heapArray[largerChild];
index = largerChild; // 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
if (oldValue < newValue) // if raised,
trickleUp(index); // trickle it up
else
// if lowered,
trickleDown(index); // trickle it down
return true;
} // end change()
// -------------------------------------------------------------
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
// heap.java
// demonstrates heaps
// to run this program: C>java HeapApp
////////////////////////////////////////////////////////////////
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 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 && 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 largerChild;
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
if (rightChild < currentSize && // (rightChild exists?)
heapArray[leftChild].getKey() < heapArray[rightChild].getKey())
largerChild = rightChild;
else
largerChild = leftChild;
// top >= largerChild?
if (top.getKey() >= heapArray[largerChild].getKey())
break;
// shift child up
heapArray[index] = heapArray[largerChild];
index = largerChild; // 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
if (oldValue < newValue) // if raised,
trickleUp(index); // trickle it up
else
// if lowered,
trickleDown(index); // trickle it down
return true;
} // end change()
// -------------------------------------------------------------
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
测试类：
package chap12;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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;
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);
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
// //////////////////////////////////////////////////////////////
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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;
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);
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
// //////////////////////////////////////////////////////////////