<pre name="code" class="plain">//从大牛那里转来的最小堆的动态添加与删除，以后好好看
public class Node {/** * 堆结点 * 节点数据类型为：int */private int iDate;public Node(int iDate) {super();this.iDate = iDate;}public int getiDate() {return iDate;}public void setiDate(int iDate) {this.iDate = iDate;}}
public class MinHeap {
/**
* 最小堆实现
*/
private Node[] heapArray; // 堆容器
private int maxSize; //堆最大大小
private int currentSize; //堆当前大小
public MinHeap(int maxSize){ //构造最小堆
this.maxSize=maxSize;
heapArray=new Node[maxSize];
currentSize=0;
}
//自上而下扫描树，将结点换成两个子女中较大的哪一个
public void filterDown(int start, int endOfHeap) {
int i=start;
int j=2*i+1;
Node temp = heapArray[i];
while(j<=endOfHeap){//检查是否到达最后位置
//让j指向两子女中的最小点
if(j<endOfHeap && heapArray[j].getiDate()>heapArray[j+1].getiDate()){
j++;
}
if(temp.getiDate()<=heapArray[i].getiDate()){//小则不作调整
break;
}else{//当前结点大，则交换i,j
heapArray[i]=heapArray[j];
i=j;
j=2*j+1;
}
}
heapArray[i] = temp;//回送
}
// 自下而上的调整:从结点start开始到0为止，自下向上比较，如果子女的值小于双亲结点的值则互相交换
public void filterUp(int start) {
int j=start;
int i=(j-1)/2;
Node temp = heapArray[j];
while(j>0){ // 沿双亲结点路径向上直达根节点
if(heapArray[i].getiDate()<=temp.getiDate()){// 双亲结点值小，不调整
break;
}else{
heapArray[j] = heapArray[i];
j = i;
i = (i - 1) / 2;
}
}
heapArray[j] = temp; // 回送
}
//插入元素，根据当前关键字构建结点，从上下扫描成功则插入，并且将堆的大小+1
public boolean insert(int key) throws MinHeapException {
boolean bool = true;
if (isFull()) {
bool = false;
throw new MinHeapException("MinHeap is full!");
} else {
Node newNode = new Node(key);
heapArray[currentSize] = newNode;
filterUp(currentSize);
currentSize++;
}
return bool;
}
//删除最小元素，先删除根节点，然后自下向上扫描，重新建立堆结构
public Node removeMin() throws MinHeapException {
if (isEmpty()) {
throw new MinHeapException("MinHeap is empty!");
}
Node root = heapArray[0];
heapArray[0] = heapArray[currentSize - 1];
currentSize--;
filterDown(0, currentSize - 1);
return root;
}
/**
* 按某种格式输出堆
*/
public void displayHeap() {
System.out.print("heapArray: ");
for (int i = 0; i < currentSize; i++) {
if (heapArray[i] != null) {
System.out.print(heapArray[i].getiDate() + " ");
} else {
System.out.print("-- ");
}
}
System.out.println();
int nBlanks = 32; // heap format
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(" ");
}
}
System.out.print(heapArray[j].getiDate()); // display item
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(); // next row
} else { // next item on row
for (int k = 0; k < nBlanks * 2 - 2; k++) {
System.out.print(' '); // interim blanks
}
}
}
System.out.println("\n" + dots + dots);
}
public boolean isEmpty() {
return currentSize == 0;
}
public boolean isFull() {
return currentSize == maxSize;
}
public void makeEmpty() {
currentSize = 0;
}
}
public class MinHeapException extends Exception { /** * */ private static final long serialVersionUID = 1L; public MinHeapException() { super("MinHeapException"); } public MinHeapException(String exMsg) { super(exMsg); } }
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/** * 最小堆应用测试 */public class MinHeapApp { /** * @param args * @throws IOException * @throws MinHeapException */ public static void main(String[] args) throws IOException, MinHeapException { int value, value2; MinHeap hp = new MinHeap(31); boolean success; hp.insert(53); hp.insert(17); hp.insert(78); hp.insert(9); hp.insert(45); hp.insert(65); hp.insert(87); hp.insert(23); while (true) { System.out.print("Enter first letter of "); System.out.print("show, insert, remove: "); int choice = getChar(); switch (choice) { case 's': hp.displayHeap(); break; case 'i': System.out.print("Enter value to insert: "); value = getInt(); success = hp.insert(value); if (!success) { System.out.println("Can't insert; heap is full"); } break; case 'r': if (!hp.isEmpty()) { hp.removeMin(); } else { System.out.println("Can't remove; heap is empty"); } break; default: System.out.println("Invalid entry\n"); } } } /** * 获得控制台输入流 * * @return * @throws IOException */ public static String getString() throws IOException { return new BufferedReader(new InputStreamReader(System.in)).readLine(); } /** * 获得控制台输入字符 * * @return * @throws IOException */ public static char getChar() throws IOException { return getString().charAt(0); } /** * 获得控制台输入整型 * * @return * @throws NumberFormatException * @throws IOException */ public static int getInt() throws NumberFormatException, IOException { return Integer.parseInt(getString()); }}
