贡献给有一定java基础的人，啥也不说了，直接上代码了。
package org.index;
import java.util.ArrayList;
import java.util.List;
import javax.sound.sampled.ReverbType;
public class MinRoot {
private Term5Num[] heapArray; // 堆容器
private int maxSize; //
堆得最大大小
private int currentSize;
// 堆大小
public MinRoot(int
_maxSize) {
maxSize = _maxSize;
heapArray = new Term5Num[maxSize];
currentSize = 0;
}
public void
filterDown(int start, int endOfHeap) {
int i = start;
int j = 2 * i + 1; // j是i的左子女位置
Term5Num temp = heapArray[i];
while (j <= endOfHeap) { //
检查是否到最后位置
if (j
< endOfHeap // 让j指向两子女中的小者
&&
heapArray[j].getNum() > heapArray[j + 1].getNum()) {
j++;
}
if
(temp.getNum() <= heapArray[j].getNum()) { // 小则不做调整
break;
} else {
// 否则小者上移，i，j下降
heapArray[i] = heapArray[j];
i = j;
j = 2 * j + 1;
}
}
heapArray[i] = temp;
}
public void filterUp(int
start) {
int j = start;
int i = (j - 1) / 2;
Term5Num temp = heapArray[j];
while (j > 0) { // 沿双亲结点路径向上直达根节点
if
(heapArray[i].getNum() <= temp.getNum()) {//
双亲结点值小，不调整
break;
} else {//
双亲结点值大，调整
heapArray[j] = heapArray[i];
j = i;
i = (i - 1) / 2;
}
heapArray[j] = temp; // 回送
}
}
public boolean
insert(Term5Num tNum) throws MinRootException {
boolean bool = true;
if (isFull()) {
//
bool =
false;
//
throw new
MinRootException("MinRoot is full!");
//满 了，就要判断当前插入的这个元素与最小值heapArray[0]的大小
if (tNum.getNum() <=
heapArray[0].getNum()) {
return false;
}
//删掉heapArray[0]，调整
removeMin();
insert(tNum);
} else {
//
Term5Num
newTerm5Num = new Term5Num(tNum);
heapArray[currentSize] = tNum;
filterUp(currentSize);
currentSize++;
}
return bool;
}
public Term5Num
removeMin() throws MinRootException {
if (isEmpty()) {
throw new
MinRootException("MinRoot is empty!");
}
Term5Num root = heapArray[0];
heapArray[0] = heapArray[currentSize - 1];
currentSize--;
filterDown(0, currentSize - 1);
return root;
}
// public void
intelligentInsert(Term5Num term5Num) throws MinRootException{
// if (currentSize
< maxSize) {
// insert(term5Num);
// }
// }
public void
displayHeap() {
System.out.print("heapArray: ");
for (int i = 0; i < currentSize;
i++) {
if
(heapArray[i] != null) {
System.out.print(heapArray[i].getNum() + " ");
} 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].getNum()); // 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 Term5Num[] getHeapArray() {
return heapArray;
}
public static void main(String[] args) throws MinRootException
{
// TODO Auto-generated method stub
Term5Num one = new Term5Num(new Term("a1", "b1", "c1"),
1);
Term5Num two = new Term5Num(new Term("a2", "b2", "c2"),
5);
Term5Num three = new Term5Num(new Term("a3", "b3", "c3"),
9);
Term5Num four = new Term5Num(new Term("a4", "b4", "c4"),
3);
Term5Num five = new Term5Num(new Term("a5", "b5", "c5"),
7);
Term5Num six = new Term5Num(new Term("a6", "b6", "c6"),
0);
Term5Num seven = new Term5Num(new Term("a7", "b7", "c7"),
1);
Term5Num eight = new Term5Num(new Term("a8", "b8", "c8"),
2);
Term5Num nine = new Term5Num(new Term("a9", "b9", "c9"),
15);
Term5Num ten = new Term5Num(new Term("a10", "b10", "c10"),
0);
MinRoot minRoot = new MinRoot(5);
minRoot.insert(one);
minRoot.insert(two);
minRoot.insert(three);
minRoot.insert(four);
minRoot.insert(five);
minRoot.insert(six);
minRoot.insert(seven);
minRoot.insert(eight);
minRoot.insert(nine);
minRoot.insert(ten);
Term5Num[] array = minRoot.getHeapArray();
for (Term5Num single : array) {
System.out.println(single.getNum());
}
}
}
@SuppressWarnings("serial")
class MinRootException extends Exception {
public
MinRootException() {
super("MinHeapException");
}
public
MinRootException(String exMsg) {
super(exMsg);
}
}
加载中，请稍候......
加载中…
喜欢