大顶堆/小顶堆

小顶堆

小顶堆是堆顶元素最小（控制堆中元素个数，比堆顶元素大的元素才能入堆，可以用来确定第k大的数）

class MinHeap{
    private int capacity;
    private int count;
    private int[] elements;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        elements = new int[capacity];
    }

    public void insert(int num) {
        if (count >= capacity) return;
        elements[count] = num; // 新加入的元素放堆底部
        // 从底部向上调整
        int pos = count;
        while (pos > 0 && elements[pos] < elements[(pos - 1) / 2]) {
            swap(pos, (pos - 1) / 2);
            pos = (pos - 1) / 2;
        }
        count++;
    }

    public void poll() {
        if (count == 0) return;

        //将堆底元素放入堆顶，相当于移除了堆顶元素
        elements[0] = elements[--count];
        // 从上向下进行调整
        int pos = 0;
        while (true) { 
            // 将当前节点值与左右节点的较小值进行交换
            int targetPos = pos;
            if (2 * pos + 1 < count && elements[targetPos] > elements[2 * pos + 1]) targetPos = 2 * pos + 1;
            if (2 * pos + 2 < count && elements[targetPos] > elements[2 * pos + 2]) targetPos = 2 * pos + 2;
            if (targetPos == pos) break; // 说明已经调整完了
            swap(pos, targetPos);
            pos = targetPos;
        } 
    } 

    public int peek() { 
        return elements[0];
    }

    public int size() {
        return this.count;
    }
    private void swap(int a, int b) {
        int tmp = elements[a];
        elements[a] = elements[b];
        elements[b] = tmp;
    }
}
           

大顶堆

参考小顶堆实现

class MaxHeap {
    private int capacaty;
    private int count;
    private int[] elements;
    
    public MaxHeap(int capacity) {
        this.capacaty = capacity;
        elements = new int[capacity];
    }
    
    public void insert(int num) {
        if (count >= capacaty) return;
        elements[count] = num;
        
        int pos = count;
        while (pos > 0 && elements[pos] > elements[(pos - 1) / 2]) {
            swap(pos, (pos - 1) / 2);
            pos = (pos - 1) / 2;
        }
        
        count++;
    }
    
    public Integer poll() {
        if (count <= 0) return null;
        int res = elements[0];
        
        int pos = 0;
        elements[pos] = elements[--count];
        
        while (true) {
            int targetPos = pos;
            if (2 * pos + 1 < count && elements[targetPos] < elements[2 * pos + 1]) targetPos = 2 * pos + 1;
            if (2 * pos + 2 < count && elements[targetPos] < elements[2 * pos + 2]) targetPos = 2 * pos + 2;
            if (targetPos == pos) break;
            swap(pos, targetPos);
            pos = targetPos;
        }
        
        return res;
    }
    
    private void swap(int a, int b) {
        int tmp = elements[a];
        elements[a] = elements[b];
        elements[b] = tmp;
    }
    
    public int size() {return this.count;}
    public int peek() {return elements[0];}
}