Heap

BigHeap.java

class BigHeap {
    // 大根堆, 大顶堆, 最大堆
    int capacity = 0;  // 容量
    int size = 0;  // 当前大小
    int[] hp;  // 数组模拟堆, 本实现使用数组下标 0 位置

    public BigHeap(int k) {
        capacity = k;
        hp = new int[capacity];
    }

    public int size() {
        return size;
    }

    public int getTop() {
        return hp[0];
    }

    public int[] getHeap() {
        return hp;
    }

    public void push(int n) {
        if (capacity == 0) return;  // capacity 为 0, 无法 push
        if (size < capacity) {
            // 未满, 直接放到末尾, 并作上浮
            hp[size++] = n;
            floatUp(size - 1);
        }
        else {
            // 已满
            if (n <= hp[0]) {
                // 小于堆顶则 pop, 然后 push
                pop();
                push(n);
            }
        }
    }

    public int pop() {
        int top = hp.length > 0 ? hp[0] : -1;
        swap(0, size - 1);  // 交换堆顶和末尾
        size--;
        sinkDown(0);  // 将堆顶下沉
        return top;
    }

    private void swap(int a, int b) {
        int t = hp[a];
        hp[a] = hp[b];
        hp[b] = t;
    }

    private void floatUp(int child) {
        if (child == 0) return;
        int farther = (child - 1) / 2;
        if (hp[child] <= hp[farther]) return;  // 不大于父节点, 无需上浮
        swap(farther, child);
        floatUp(farther);
    }

    private void sinkDown(int farther) {
        int left = farther * 2 + 1;
        int right = (farther + 1) * 2;
        int maxChild;
        if (left >= size) return;  // 左节点已溢出, 直接返回
        if (right < size) maxChild = hp[left] > hp[right] ? left : right;  // 右节点未溢出, 取左右值较大者的下标
        else maxChild = left;  // 右节点溢出, 直接取左节点
        if (hp[farther] >= hp[maxChild]) return;  // 父节点不小于子节点, 无需下沉
        else swap(farther, maxChild);
        sinkDown(maxChild);  // 递归下沉, 直到满足跳出条件
    }
}

SmallHeap.java

class SmallHeap {
    // 小根堆, 小顶堆, 最小堆
    int capacity = 0;  // 容量
    int size = 0;  // 当前大小
    int[] hp;  // 数组模拟堆, 本实现使用数组下标 0 位置

    public SmallHeap(int k) {
        capacity = k;
        hp = new int[capacity];
    }

    public int size() {
        return size;
    }

    public int getTop() {
        return hp[0];
    }

    public int[] getHeap() {
        return hp;
    }

    public void push(int n) {
        if (capacity == 0) return;  // capacity 为 0, 无法 push
        if (size < capacity) {
            // 未满, 直接放到末尾, 并作上浮
            hp[size++] = n;
            floatUp(size - 1);
        }
        else {
            // 已满
            if (n >= hp[0]) {
                // 小于堆顶则 pop, 然后 push
                pop();
                push(n);
            }
        }
    }

    public int pop() {
        int top = hp.length > 0 ? hp[0] : -1;
        swap(0, size - 1);  // 交换堆顶和末尾
        size--;
        sinkDown(0);  // 将堆顶下沉
        return top;
    }

    private void swap(int a, int b) {
        int t = hp[a];
        hp[a] = hp[b];
        hp[b] = t;
    }

    private void floatUp(int child) {
        if (child == 0) return;
        int farther = (child - 1) / 2;
        if (hp[child] >= hp[farther]) return;  // 不小于父节点, 无需上浮
        swap(farther, child);
        floatUp(farther);
    }

    private void sinkDown(int farther) {
        int left = farther * 2 + 1;
        int right = (farther + 1) * 2;
        int minChild;
        if (left >= size) return;  // 左节点已溢出, 直接返回
        if (right < size) minChild = hp[left] < hp[right] ? left : right;  // 右节点未溢出, 取左右值较小者的下标
        else minChild = left;  // 右节点溢出, 直接取左节点
        if (hp[farther] <= hp[minChild]) return;  // 父节点不大于子节点, 无需下沉
        else swap(farther, minChild);
        sinkDown(minChild);  // 递归下沉, 直到满足跳出条件
    }
}