minheap.java

来自「图论中关于简单无向图的深度」· Java 代码 · 共 67 行

/**
 * <p>Title: </p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2005</p>
 * <p>Company: </p>
 * @author not attributable
 * @version 1.0
 */

public class MinHeap {
  //最小堆，计算最小生成树时使用
    private Edge[] heap;
    private int currentSize;
    /** Creates a new instance of MinHeap */
    public MinHeap(int maxSize) {
        heap=new Edge[maxSize];
        currentSize=0;
    }

    public void Insert(Edge x){
        heap[currentSize]=x;
        FilterUp(currentSize);
        currentSize++;
    }

    public Edge RemoveMin(){
        Edge x=heap[0];
        heap[0]=heap[currentSize-1];
        currentSize--;
        FilterDown(0,currentSize-1);
        return x;
    }

    private void FilterDown(int start,int end){
        int i=start,j=2*i+1;
        Edge temp=heap[i];
        while(j<=end){
            if(j<end&&heap[j].weight>heap[j+1].weight)
                j++;
            if(temp.weight<=heap[j].weight) break;
            else{
                heap[i]=heap[j];
                i=j;
                j=2*i+1;
            }
        }
        heap[i]=temp;
    }

    private void FilterUp(int start){
        int j=start,i=(j-1)/2;
        Edge temp=heap[j];
        while(j>0){
            if(heap[i].weight<=temp.weight)break;
            else{
                heap[j]=heap[i];
                j=i;
                i=(i-1)/2;
            }
        }
        heap[j]=temp;
    }

}