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类中的一个生成随机数组的函数 结果如图: