Java实现堆

使用优先队列实现堆
class MaxHeap {
    private int[]data ;
    private int count ;
    private int capacity;

    public MaxHeap(int capacity) {
        data = new int[capacity + 1];
        count=0 ;
    }

    public int size() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }
    public void insert(int item) {
        assert count + 1 <= capacity;
        // 把新添加的元素放在数组的最后一位，对应于最大堆最后一个叶子结点
        data[count + 1] = item;
        count++;
        // 考虑将它上移
        siftUp(count);
    }

    private void siftUp(int k) {
        int temp = data[k];

        while (k > 1 && data[k/2] < temp){
            swap(data,k/2,k);
            k /= 2;
        }
    }

    private void swap(int[] data, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        int temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }

    public int extractMax() {
        assert count > 0;
        int ret = data[1];
        swap(data, 1, count);
        count--;
        shiftDown(1);
        return ret;
    }

    private void shiftDown(int h) {
        while (2 * h <= count) {
            int k = 2 * h ;
            if (k + 1<= count && data[k + 1] > data[k]) {
                k = k + 1;
            }

            if (data[h] < data[k]) {
                swap(data,h,k);
            }
            h *= 2;
        }
    }


}