自建堆

这是大顶堆
建堆heapify()和取最大值delMax()都是用的下滤percolateDown()
实现下滤可以借助swap()和properParent()--找到三者中的最大值的秩--可以比较简洁实现。
上滤的话注意循环退出条件要注意parent==pos，避免进入死循环

class Heap{
    int data[];
    int size;
    int capacity;
    Heap(int[] data){
        this.data=data;
        size=data.length;
        heapify();
    }
    Heap(int n){
        capacity=n;
        size=0;
        data=new int[n];
    }
    void  insert(int num){
        if(size==capacity)return;
        data[size]=num;
        size++;
        percolateUp(size-1);
    }
    int delMax(){
        if(size==0)return -1;
        int max=data[0];
        data[0]=data[size-1];
        size--;
        percolateDown(0);
        return max;
    }
    void heapify(){
       for(int i=(size-2)/2;i>=0;i--){
           percolateDown(i);
       }
    }
    int properParent(int i,int j,int k){
        int maxPos=i;
        if(j<size&&data[j]>data[maxPos])
               maxPos=j;
        if(k<size&&data[k]>data[maxPos])
               maxPos=k;
        return maxPos;
    }
    //下滤
    int percolateDown(int pos){//对秩为pos的节点进行下滤
         int j;
      while(pos!=(j=properParent(pos,pos*2+1,pos*2+2))){
          swap(pos,j);//交换前j对应三者中最大的元素，交换后j对应原来pos对应的值；
          pos=j;
      }
      return pos;
    }
    //上滤
    int percolateUp(int pos){
        while((pos-1)/2>=0){
            int parent=(pos-1)/2;
            if(parent==pos||data[parent]>data[pos])
                break;
            swap(parent,pos);
            pos=parent;
        }
        return pos;
    }

    void swap(int i,int j){
        int temp=data[i];
        data[i]=data[j];
        data[j]=temp;
    }
}

自建堆

原文：https://www.cnblogs.com/wsshub/p/14728424.html