Heap的java實作

<span style="font-size:32px;">package com.liebao34;

public class Heap {
	private Node[] heapArr;
	private int maxSize;
	private int currentSize;
	public Heap(int mx){
		maxSize = mx;
		currentSize = 0;
		heapArr = new Node[maxSize];
	}
	public boolean isEmpty(){
		return currentSize==0;
	}
	
	public boolean insert(int key){
		if(currentSize==maxSize)
			return false;
		Node newNode = new Node(key);
		heapArr[currentSize] = newNode;
		trickleUp(currentSize);
		currentSize++;
		return true;
	}
	
	public void trickleUp(int index){
		int parent = (index-1)/2;
		Node bottom = heapArr[index];
		while(index>0 && heapArr[parent].getKey()<bottom.getKey()){
			heapArr[index] = heapArr[parent];
			index = parent;
			parent = (parent-1)/2;
		}
		heapArr[index] = bottom;
	}
	
	public Node remove(){
		Node root = heapArr[0];
		heapArr[0] = heapArr[--currentSize];
		trickleDown(0);
		return root;
	}
	
	public void trickleDown(int index){
		int largeChild;
		Node top = heapArr[index];
		while(index<currentSize/2){
			int leftChild = 2*index+1;
			int rightChild = leftChild+1;
			if(rightChild<currentSize&&heapArr[leftChild].getKey()<heapArr[rightChild].getKey()){
				largeChild = rightChild;
			}else{
				largeChild = leftChild;
			}
			if(top.getKey()>=heapArr[largeChild].getKey())break;//no need to exchange
			heapArr[index]=heapArr[largeChild];
			index = largeChild;
		}
		heapArr[index] = top;
	}
	public boolean change(int index,int newValue){
		if(index<0||index>=currentSize){
			return false;
		}
		int oldValue = heapArr[index].getKey();
		heapArr[index].setKey(newValue);
		if(oldValue<newValue){
			trickleUp(index);
		}else{
			trickleDown(index);
		}
		return true;
	}
	
	public void displayHeap(){
		System.out.println("HeapArray: ");
		for(int i=0;i<currentSize;i++){
			if(heapArr[i]!=null){
				System.out.print(heapArr[i].getKey()+" ");
			}else {
				System.out.print("-- ");
			}
		}
		System.out.println();
		//display by tree
		int nBlanks = 32;
		int itemPerRow = 1;
		int column = 0;
		int j=0;
		String dot = "............";
		System.out.println(dot+dot);
		while (currentSize>0) {
			if(column==0){
				for(int k =0;k<nBlanks;k++){
					System.out.print(" ");
				}
			}
			System.out.print(heapArr[j].getKey());
			if(++j==currentSize)break;
			if(++column==itemPerRow){
				nBlanks/=2;
				itemPerRow*=2;
				column=0;
				System.out.println();
			}else{
				for(int k=0;k<nBlanks*2-2;k++){
					System.out.print(" ");
				}
			}
		}
		System.out.println("\n"+dot+dot);
	}
}
</span>
           

<span style="font-size:32px;">
</span>
           

<pre name="code" class="java"><span style="font-size:32px;">package com.liebao34;

public class Node {
	private int iData;
	public Node(int key){
		iData = key;
	}
	public int getKey(){
		return iData;
	}
	public void setKey(int id){
		iData = id;
	}
}
</span>
           

<pre name="code" class="java"><span style="font-size:32px;">package com.liebao34;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class HeapApp {
	public static void main(String[] args) throws Exception{
		int value,value2;
		Heap theHeap = new Heap(31);
		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);
		while(true){
			System.out.print("Enter first letter: show,change,insert,remove,change:");
			char choice = getChar();
			switch (choice) {
			case 's':
				theHeap.displayHeap();
				break;
			case 'i':
				System.out.print("Enter value to insert: ");
				value = getInt();
				success = theHeap.insert(value);
				if(!success){
					System.out.print("Cna not insert,heap is full!");
				}
				break;
			case 'r':
				if(!theHeap.isEmpty()){
					theHeap.remove();
				}else{
					System.out.println("can not remove,heap is empty");
				}
				break;
			case 'c':
				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 input!\n");
			}
		}
	}
	
	public static String getString() throws IOException{
		InputStreamReader isr = new InputStreamReader(System.in);
		BufferedReader br = new BufferedReader(isr);
		return br.readLine();
	}
	
	public static char getChar() throws IOException{
		return getString().charAt(0);
	}
	
	public static int getInt() throws IOException{
		return Integer.parseInt(getString());
	}
}</span>
           

輸出:

<pre name="code" class="java"><span style="font-size:32px;">Enter first letter: show,change,insert,remove,change:s
HeapArray: 
100 90 80 30 60 50 70 20 10 40 
........................
                                100
                90                              80
        30              60              50              70
    20      10      40
........................
Enter first letter: show,change,insert,remove,change:i
Enter value to insert: 77
Enter first letter: show,change,insert,remove,change:i
Enter value to insert: 120
Enter first letter: show,change,insert,remove,change:s
HeapArray: 
120 90 100 30 77 80 70 20 10 40 60 50 
........................
                                120
                90                              100
        30              77              80              70
    20      10      40      60      50
........................
Enter first letter: show,change,insert,remove,change:c
Enter current index of item.3
Enter new key: 33
Enter first letter: show,change,insert,remove,change:s
HeapArray: 
120 90 100 33 77 80 70 20 10 40 60 50 
........................
                                120
                90                              100
        33              77              80              70
    20      10      40      60      50
........................
Enter first letter: show,change,insert,remove,change:c
Enter current index of item.3
Enter new key: 130
Enter first letter: show,change,insert,remove,change:s
HeapArray: 
130 120 100 90 77 80 70 20 10 40 60 50 
........................
                                130
                120                              100
        90              77              80              70
    20      10      40      60      50
........................
Enter first letter: show,change,insert,remove,change:</span>
           

堆的特點：

<span style="font-size:32px;">1.它是一種完全二叉樹，除了樹的最後一個節點不需要是滿的，其他的每一層從左到右都完全是滿的；</span>
           

<span style="font-size:32px;">2.它常常使用數組實作的；</span>
           

<span style="font-size:32px;">3.堆中的每個節點都滿足堆的條件，父親節點的關鍵字要大于子節點；</span>
           

<span style="font-size:32px;">4.堆是弱序的.</span>