Java-最大ヒープを手動で実現

具体的な実装:

               ，          ，         ：
1）      （                    ）
2）              

      ，   0  ，      ：
   ： 2*i + 1
   ： 2*i + 2
   ：（i - 1）/2

コード:
1、まずクラスの基礎変数といくつかの簡単な方法で、主に補助方法である.

public class BinaryHeap> {
    private ArrayList data;

    public BinaryHeap(int capacity){
        data = new ArrayList<>(capacity);
    }

    public BinaryHeap(){
        data = new ArrayList<>();
    }

    //       
    public int size(){
        return data.size();
    }

    //        
    public boolean isEmpty(){
        return data.isEmpty();
    }

    //    。        
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("it is root");
        return (index - 1)/2;
    }
    private int leftchild(int index){
        return 2*index + 1;
    }
    private int rightchild(int index){
        return 2*index + 2;
    }

2、上記のコードに続き、これはスタックにノードを追加します.完全なツリーの性質のため、追加要素は、追加するノードを最後のレイヤの末尾に配置し、その後、親ノードと比較し続け、適切な位置を選択します.このプロセスを上へ移動と呼びます.

    //       ；          ，                  
    //    ，              ，       。        
    public void add(E e){
        data.add(e);
        siftUp(data.size() - 1);
    }
    //k      ，    
    private void siftUp(int k){
        // k k        ，     k ， 
        while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            //ArrayList        swap    ，                
            data.swap(k, parent(k));
            //   k             ，       
            k = parent(k);
        }
    }

3、つなぎます.これはスタックから最大の要素を取り出します.完全な二叉木の性質のため、エレメントを取り出すのは、最後のレイヤの最後のエレメントと、エレメントを取り出す位置、すなわちルートノードです.(最も大きなルートノードが最大であるため、0番目の位置で)スワップし、この位置の左右のサブツリーがこの最後のレイヤの末尾ノードより大きいかどうかを見て、それより大きい場合は、最大のノードを選択して現在のノードとスワップし、再帰的に比較し続けます.このプロセスをドロップと呼びます.詳細はコードコメントを参照してください.

    public E extractMax(E e){
        E res = lookMax();
        data.swap(0,data.size() - 1);
        data.remove(data.size() -1);
        siftDown(0);
        return res;
    }
    //      
    public E lookMax(){
        return data.get(0);
    }
    private void siftDown(int k){
        //    ，                 ，
        //             ，         ，
        //       ：leftchild < data.size()，       
        while(leftchild(k) < data.size()){
            int j = leftchild(k);
            //j+1                ，    size       
            //                       ,  0      
            if(j+1 < data.size() && data.get(j+1).compareTo(data.get(j)) > 0){
                //             j
                //   j              
                j = rightchild(k);
            }
            if(data.get(k).compareTo(data.get(j)) >= 0){
                //    k  j          
                break;
            data.swap(k, j); //    
            k = j; // j            k k  ，       
        }
    }
}

まとめ:

   ：          。     :O(logn)（            ，     ）

1.           ，   add()。

2.            ，   extractMax()。

3.      （  ），                   ，        。