Java最小スタック実装
1.スタックポイント
2.最小ヒープ
3.スタック異常
4. 最小ヒープ適用テスト
package boke.heap1;
/**
*
*
* @since jdk1.5
* @author
* @version 1.0
* @date 2010.05.24
*
*/
public class Node {
private int iData; //
public Node(int key) {
iData = key;
}
/**
* setKey
*
* @param id
*/
public void setKey(int id) {
iData = id;
}
/**
* getKey
*
* @return
*/
public int getKey() {
return iData;
}
}
2.最小ヒープ
package boke.heap1;
import boke.heap.Node;
/**
*
*
* @since jdk1.5
* @author
* @version 1.0
* @date 2010.05.24
*
*/
public class MinHeap {
private Node[] heapArray; //
private int maxSize; //
private int currentSize; //
public MinHeap(int _maxSize) {
maxSize = _maxSize;
heapArray = new Node[maxSize];
currentSize = 0;
}
/**
*
*
* @param start
* @param endOfHeap
*/
public void filterDown(int start, int endOfHeap) {
int i = start;
int j = 2 * i + 1; // j i
Node temp = heapArray[i];
while (j <= endOfHeap) { //
if (j < endOfHeap // j
&& heapArray[j].getKey() > heapArray[j + 1].getKey()) {
j++;
}
if (temp.getKey() <= heapArray[j].getKey()) { //
break;
} else { // ,i,j
heapArray[i] = heapArray[j];
i = j;
j = 2 * j + 1;
}
}
heapArray[i] = temp;
}
/**
* : start 0 , ,
*
* @param start
*/
public void filterUp(int start) {
int j = start;
int i = (j - 1) / 2;
Node temp = heapArray[j];
while (j > 0) { //
if (heapArray[i].getKey() <= temp.getKey()) {// ,
break;
} else {// ,
heapArray[j] = heapArray[i];
j = i;
i = (i - 1) / 2;
}
heapArray[j] = temp; //
}
}
/**
*
*
* @param key
* @return
* @throws MinHeapException
*/
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;
}
/**
*
*
* @return
* @throws MinHeapException
*/
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].getKey() + " ");
} 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].getKey()); // 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("
" + dots + dots);
}
public boolean isEmpty() {
return currentSize == 0;
}
public boolean isFull() {
return currentSize == maxSize;
}
public void makeEmpty() {
currentSize = 0;
}
}
3.スタック異常
package boke.heap1;
/**
*
*
* @since jdk1.5
* @author
* @version 1.0
* @date 2010.05.24
*
*/
public class MinHeapException extends Exception {
public MinHeapException() {
super("MinHeapException");
}
public MinHeapException(String exMsg) {
super(exMsg);
}
}
4. 最小ヒープ適用テスト
package boke.heap1;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
*
*
* @since jdk1.5
* @author
* @version 1.0
* @date 2010.05.24
*
*/
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
");
}
}
}
/**
*
*
* @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());
}
}