Java實作二叉堆

堆(Heap)是一類特殊的資料結構的統稱。堆通常是一個可以被看做一棵完全二叉樹的數組對象。

在二叉堆中，從任意結點向上，我們都能得到一列非遞減的元素；從任意結點向下，我們都能得到一列非遞增的元素。

在堆中有兩個特殊的操作：

1. 上浮(swim)：

如果堆的有序狀态因為某個結點變得比它父結點更大而打破，那麼我們就需要進行上浮操作。

1. 下沉(sink):

如果堆的有序狀态因為某個結點變得比它的兩個子節點或者其中之一更小而打破，那麼我們就需要進行下沉操作。

插入元素：

将新元素添加到元素末尾，增加堆的大小并讓這個新的元素上浮到合适的位置。

删除最大元素：

将數組最後一個元素和堆頂元素交換，減小數組大小并讓這個元素下沉到合适的位置

具體實作代碼如下：

/**
 * 大頂堆
 * @param <Item> 鍵
 */
public class MaxPQ <Item extends Comparable<Item>> {

    private int N;
    private Item[] pq;   //利用數組表示堆

    public MaxPQ() {
    	N = 0;
        pq = (Item[]) new Comparable[2];
    }

    /**
     * 調整數組大小
     * @param size  調整後的數組大小
     */
    private void resize(int size) {
        Comparable[] a = new Comparable[size];
        for (int i = 1; i <= N; i++) {
            a[i] = pq[i];
        }
        pq = (Item[]) a;
    }

    /**
     *
     * @param i 索引i
     * @param j 索引j
     * @return  索引為i的元素是否小于索引為j的元素
     */
    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    /**
     * 交換元素
     * @param i 索引i
     * @param j 索引j
     */
    private void exch(int i, int j) {
        Item t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }

    /**
     * 上浮:如果某個結點比它的父結點要大，采取該操作
     * @param k 結點的位置
     */
    private void swim(int k) {
        while (k > 1) {
            if (less(k/2, k)) {
                exch(k/2, k);
                k = k/2;
            }
        }
    }

    /**
     * 下沉
     * @param k 結點的位置
     */
    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) {
                j++;
            }
            if (less(j, k)) {
                break;
            }
            exch(k, j);
            k = j;
        }
    }

    /**
     *
     * @return  堆是否為空
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     *
     * @return  堆中元素個數
     */
    public int size() {
        return N;
    }

    /**
     * 插入元素
     * @param Item   要插入的元素
     */
    public void insert(Item item) {
        if (N == pq.length-1) {
            resize(2*pq.length);
        }
        pq[++N] = item;
        swim(N);
    }

    /**
     * 删除并傳回最大元素
     * @return  最大元素
     */
    public Item delMax() {
        if (N == pq.length/4) {
            resize(pq.length/2);
        }
        Item max = pq[1];
        exch(1, N--);
        pq[N+1] = null;
        sink(1);
        return max;
    }

    /**
     * 
     * @return  堆中最大值
     */
    public Item max() {
        return pq[1];
    }

    /**
     * 
     * @return  堆中最小值
     */
    public Item min() {
        int min = N;
        for (int i = N; i >= 1; i--) {
            if (less(i, min)) {
                min = i;
            }
        }
        return pq[min];
    }

    /**
     *
     * @param item  所要查找的元素
     * @return  該元素是否存在
     */
    public boolean contains(Item item) {
        for (int i = 1; i <= N; i++) {
            if (pq[i] == item) {
                return true;
            }
        }
        return false;
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            s.append(pq[i] + " ");
        }
        return s.toString();
    }

    public static void main(String[] args) {
        MaxPQ<Integer> maxPQ = new MaxPQ<>();
        for (int i = 1; i <= 24; i++) {
            maxPQ.insert(i);
        }
        System.out.println(maxPQ.toString());
        System.out.println(maxPQ.size());
        System.out.println(maxPQ.max());
        System.out.println(maxPQ.min());
        System.out.println(maxPQ.contains(0));
        maxPQ.delMax();
        System.out.println(maxPQ.toString());
    }

}