java實作最小堆(通過構造函數構造最小堆，相當于堆排序)

最小堆

最小堆資料結構也是一棵完全二叉樹（ 葉節點隻能出現在最下層和次下層，并且最下面一層的結點都集中在該層最左邊的若幹位置的二叉樹）。

因為完全二叉樹的性質，是以我們用數組來存儲樹的節點，從上到下,從左到右,按序存在數組,而且子節點的值得大于等于父節點的值。是以堆的根節點是數組中的最小值，這即是最小堆。 下面最小堆的實作:

//最小堆
public class MinHeap {
	private int[] data;
	private int count; //目前節點數
	private int capacity; //容量
	
	private void shiftDown(int k){
		while((2*k)<=count){     //有左子節點
			 int j=2*k;      //這輪循環,data[k]和data[j]交換位置
			 if((j+1)<=count&&(data[j+1]<data[j])){ //有右子節點且右邊的更小
				 j+=1;
			 }
			 if(data[k]<=data[j])  //如果父節點小于等于子節點,則停止循環
				 break;
			 swap(data,k,j);
			 k=j;       //k被賦為目前位置,為下次循環做初始化
		}
	}
	
	public static void swap(int[] arr,int a,int b){
		int c=arr[a];
		arr[a]=arr[b];
		arr[b]=c;
	}
	public MinHeap(int capacity) {
		this.data=new int[capacity+1];  //因為索引0不存節點，是以長度加一
		this.capacity=capacity;
		this.count=0;
	}
	//将一個無序數組構造成一個最小堆          相當于堆排序
	public MinHeap(int[] arr,int n){
		data=new int[n+1];
		capacity=n;
		for(int i=0;i<n;i++){
			data[i+1]=arr[i];
		}
		count=n;
		for(int i=count/2;i>=1;i--){  //i=count/2:i是最後一個葉子節點的父節點(最後一個非葉子節點)
			shiftDown(i);
		}
	}
	
	public int extractMin(){      //彈出最小值，即根節點
		assert(count>0);
		int ret=data[1];
		swap(data,1,count);    //将最後數放到第一位置,保持完全二叉樹的結構
		count--;
		shiftDown(1);         //将第一個數移至合适位置,保持最小堆性質
		return ret;
	}
	
	public int size() {
		return count;
	}
	public boolean isEmpty(){
		return count==0;
	}
	public static void main(String[] args) {
		int arr[] =MAIN.geneateArrays(40);
		MinHeap mp=new MinHeap(arr,arr.length);
		System.out.print("heap.extractMin():");
		while(!mp.isEmpty()){
			System.out.print(mp.extractMin()+" ");   //從小到大輸出
		}
	}

}
           

MAIN.geneateArrays(40)是我寫的MAIN類中的一個生成随機數組的函數 結果如圖: