資料結構---二叉堆

二叉堆(也成為堆)是一棵被完全填滿的二叉樹，有可能的例外實在底層，底層上的元素從左到右填入。這樣的樹稱為完全二叉樹。它可以用一個數組表示而不需要使用鍊。

對于數組中任一位置i上的元素，其左兒子在位置2i上，右兒子在左兒子後的單元(2i+1)中，它的父親則在位置[i/2]上是以周遊該樹所需要的操作極其簡單。

堆序性質：任意節點小于它的所有後裔，也就是說最小元總可以在根處找到(即最小堆)

insert操作

為了将一個元素X插入到堆中：

1. 我們在下一個可用位置創造一個空穴。如果X可以放在該空穴中而并不破壞堆的序，那麼插入完成，否則 2.
2. 把空穴的父節點上的元素移入該空穴，這樣空穴就朝着根的方向上冒一步。繼續該過程直到X能被放入空穴中為止。

這種政策一般叫做上濾

public void insert(AnyType x){
    if(currentSize == array.length - )
        //如果堆的大小不夠了就重新配置設定大小
        enlargeArray(array.length *  + );

    int hole = ++currentSize;
    //判斷條件for循環中
    for(array[] = x; x.compareTo(array[hole / ]) < ; hole /= )
        array[hole] = array[hole / ];
    array[hole] = x;
}
           

deleteMin

找出最小元是容易的，困難之處是删除它。

1. 在最小堆中删除最小元後就會在根節點建立一個空穴。由于現在堆少了一個元素，是以堆中最後一個元素X必須移動到該堆的某個地方
2. 将空穴的兩個兒子中較小者移入空穴，這樣就把空穴向下推了一層。重複該步驟直到X可以被放入空穴中。
3. 将X置入沿着從根開始包含最小兒子的一條路徑上的一個正确的位置

這種操作叫做下濾

public AnyType deleteMin(){
    if(isEmpty()){
        throw new UnderflowException();
    }
    AnyType minItem = findMin();
    array[] = array[currentSize--];
    percolateDown();

    return minItem;
}

//下濾
private void percolateDown(int hole){
    int child;
    AnyType tmp = array[hole];

    for(; hole *  <=currentSize; hole = child){
        child = hold * ;
        //(child != currentSize)保證有兩個子節點
        //同時判斷哪一個子節點可以上移
        if(child != currentSize && 
                array[child + ].compareTo(array[child]) < )
            child++;
        //對複合條件的子節點進行上移
        if(array[child].compareTo(tmp) < )
            array[hole] = array[child];
        else
            break;
    }
    array[hole] = tmp;
}
           

buildHeap

有時二叉堆是由一些項的初始集合構而得。這種構造方法以N項作為輸入，并把它們放到一個堆中。

public BinaryHeap(AnyType[] items){
    currentSize = items.length;
    array = (AnyType[]) new Comparable[(currentSize + ) *  / ];
    int i = ;
    for(AnyType item : items)
        array[i++] = item;
    buildHeap();
}

private void buildHeap(){
    for(int i = currentSize / ; i > ; i--)
        percolateDown(i);
}