优先级队列的学习(二)

Han.miracle

发布于 2025-12-22 14:43:09

文章被收录于专栏：Java核心技术图谱：原理·对比·避坑Java核心技术图谱：原理·对比·避坑

创建堆

上一节优先队列的学习讲过了，我们再看看代码这是换一种写法的代码

public static void createHeap(int[] array) {
    // 找到倒数第一个非叶子节点的索引
    int root = ((array.length - 2) >> 1); 
    // 从该节点开始，向前遍历到根节点（索引0），每个节点执行向下调整
    for (; root >= 0; root--) {
        shiftDown(array, root); 
    }
}

int root = ((array.length - 2) >> 1); 作用：计算最后一个非叶子节点的索引。原理：数组长度为 array.length，最后一个元素的索引是 array.length - 1。根据完全二叉树的性质，非叶子节点的子节点索引 = 2 * 父节点索引 + 1（左孩子）或 2*父节点索引 + 2（右孩子）。反推：最后一个非叶子节点的索引 = (最后一个元素索引 - 1) / 2，即 (array.length - 1 - 1) / 2 = (array.length - 2) / 2 ->> 1 是位运算，等价于整数除法 / 2（效率更高），因此 (array.length - 2) >> 1 与 (array.length - 2) / 2 结果相同。举例：若数组长度为 6（索引 0~5），最后一个非叶子节点索引 = (6-2)/2 = 2（正确，节点 2 的子节点是 4 和 5）。

<<（左移）：左移 1 位，数值乘以 2；左移 n 位，数值乘以 2 的n次方（不溢出时） >>（右移）：右移 1 位，数值除以 2；右移 n 位，数值除以 2 的n次方（不溢出时）

（无符号右移）：右移 1 位，数值除以 2（取整）；右移 n 位，数值除以 (2^n)（取整）。 左移（<<）：乘 2 的 n 次幂，补 0。 带符号右移（>>）：除 2 的 n 次幂，符号位补自身。 无符号右移（>>>）：除 2 的 n 次幂，高位补 0（结果非负）。

public static void createHeap(int[] array) {
    // 找到倒数第一个非叶子节点的索引
    int root = ((array.length - 2) >> 1); 
    // 从该节点开始，向前遍历到根节点（索引0），每个节点执行向下调整
    for (; root >= 0; root--) {
        shiftDown(array, root); 
    }
}

用大堆创建向下（下沉）

public class HeapCreator {
    // 大根堆的向下调整：确保父节点 >= 子节点
    private void shiftDownMax(int[] array, int parent, int len) {
        int child = 2 * parent + 1; // 左孩子索引
        while (child < len) {
            // 找左右孩子中更大的那个
            if (child + 1 < len && array[child + 1] > array[child]) {
                child++;
            }
            // 父节点 >= 最大子节点，满足大根堆
            if (array[parent] >= array[child]) {
                break;
            }
            // 交换父节点与最大子节点
            int temp = array[parent];
            array[parent] = array[child];
            array[child] = temp;
            // 继续向下调整
            parent = child;
            child = 2 * parent + 1;
        }
    }

    // 创建大根堆
    public void buildMaxHeap(int[] array) {
        int n = array.length;
        // 从最后一个非叶子节点开始，向前调整所有非叶子节点
        for (int parent = (n - 2) / 2; parent >= 0; parent--) {
            shiftDownMax(array, parent, n);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 7, 5, 4};
        new HeapCreator().buildMaxHeap(arr);
        // 输出：7 5 4 3 1 2（满足大根堆性质）
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

向上的

public class MaxHeapWithShiftUp {
    private int[] heap;   
    private int size;      
    private int capacity; 

    // 初始化大根堆
    public MaxHeapWithShiftUp(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    // 大根堆的向上调整：新元素插入后上浮
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;  // 计算父节点索引
        // 循环条件：子节点不是根节点，且子节点值 > 父节点值（破坏大根堆性质）
        while (child > 0 && heap[child] > heap[parent]) {
            // 交换子节点与父节点（大值上浮）
            swap(child, parent);
            // 向上移动：子节点指向原父节点，重新计算父节点
            child = parent;
            parent = (child - 1) / 2;
        }
    }

    // 插入元素到大根堆
    public void insert(int value) {
        if (size == capacity) {
            throw new RuntimeException("堆已满，无法插入");
        }
        // 新元素放到堆的末尾
        heap[size] = value;
        // 对新元素执行向上调整
        shiftUp(size);
        size++;  // 元素个数加1
    }

    // 交换元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 获取堆顶元素（最大值）
    public int peek() {
        if (size == 0) {
            throw new RuntimeException("堆为空");
        }
        return heap[0];
    }

    // 测试
    public static void main(String[] args) {
        MaxHeapWithShiftUp maxHeap = new MaxHeapWithShiftUp(10);
        // 插入元素
        maxHeap.insert(3);
        maxHeap.insert(1);
        maxHeap.insert(2);
        maxHeap.insert(7);
        maxHeap.insert(5);
        maxHeap.insert(4);

        System.out.println("堆顶元素（最大值）：" + maxHeap.peek()); // 输出：7
        System.out.print("堆元素：");
        for (int i = 0; i < maxHeap.size; i++) {
            System.out.print(maxHeap.heap[i] + " "); // 输出：7 5 4 3 1 2
        }
    }
}

用小堆创建 向下的（下沉）

public class MinHeapCreator {
    // 小根堆的向下调整：确保父节点 <= 子节点
    private void shiftDownMin(int[] array, int parent, int len) {
        int child = 2 * parent + 1; // 左孩子索引
        while (child < len) {
            // 找左右孩子中更小的那个（若右孩子存在且更小，则标记右孩子）
            if (child + 1 < len && array[child + 1] < array[child]) {
                child++;
            }
            // 父节点 <= 最小子节点，满足小根堆性质，无需调整
            if (array[parent] <= array[child]) {
                break;
            }
            // 交换父节点与最小子节点（父节点下沉）
            int temp = array[parent];
            array[parent] = array[child];
            array[child] = temp;
            // 继续向下调整（父节点移至子节点位置，更新子节点索引）
            parent = child;
            child = 2 * parent + 1;
        }
    }

    // 创建小根堆
    public void buildMinHeap(int[] array) {
        int n = array.length;
        // 从最后一个非叶子节点开始，向前调整所有非叶子节点
        for (int parent = (n - 2) / 2; parent >= 0; parent--) {
            shiftDownMin(array, parent, n);
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 2, 7, 5, 4};
        new MinHeapCreator().buildMinHeap(arr);
        // 输出：1 3 2 7 5 4（满足小根堆性质：堆顶为最小值，父节点 <= 子节点）
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
向上的（上浮）

```java
public class MinHeapWithShiftUp {
    private int[] heap; 
    private int size;   
    private int capacity; 

    // 初始化堆
    public MinHeapWithShiftUp(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    // 小根堆的向上调整：插入新元素后，将其上浮到合适位置
    private void shiftUp(int child) {
        int parent = (child - 1) / 2; // 计算父节点索引
        // 循环条件：子节点不是根节点，且子节点值 < 父节点值（不满足小根堆性质）
        while (child > 0 && heap[child] < heap[parent]) {
            // 交换子节点与父节点（小值上浮）
            swap(child, parent);
            // 向上移动：子节点指向原父节点，重新计算父节点
            child = parent;
            parent = (child - 1) / 2;
        }
    }

    // 插入元素到小根堆
    public void insert(int value) {
        if (size == capacity) {
            throw new RuntimeException("堆已满，无法插入");
        }
        // 插入到堆的末尾
        heap[size] = value;
        // 对新插入的元素执行向上调整
        shiftUp(size);
        size++; // 元素个数加1
    }

    // 交换两个索引的元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 获取堆顶元素（最小值）
    public int peek() {
        if (size == 0) {
            throw new RuntimeException("堆为空");
        }
        return heap[0];
    }

    // 测试
    public static void main(String[] args) {
        MinHeapWithShiftUp minHeap = new MinHeapWithShiftUp(10);
        // 插入元素
        minHeap.insert(3);
        minHeap.insert(1);
        minHeap.insert(2);
        minHeap.insert(7);
        minHeap.insert(5);
        minHeap.insert(4);

        // 输出堆顶元素（应为最小值1）
        System.out.println("堆顶元素：" + minHeap.peek()); // 输出：1

        // 打印堆中的元素（顺序为数组存储的小根堆结构）
        System.out.print("堆元素：");
        for (int i = 0; i < minHeap.size; i++) {
            System.out.print(minHeap.heap[i] + " "); // 输出：1 3 2 7 5 4
        }
    }
}

`` 堆的调整调整步骤 初始化标记： parent 标记需要调整的节点（如根节点）。 child 标记 parent 的左孩子（child = 2parent + 1，因为完全二叉树中，若有孩子，左孩子一定存在）。 循环调整（直到 parent 无左孩子）： 若右孩子存在（child+1 < size），比较左右孩子大小，让 child 标记值更小的孩子。 比较 parent 与 child 的值： 若 parent 的值 ≤ child 的值：满足小根堆性质，调整结束。 否则：交换 parent 与 child，然后将 parent 指向 child，child 更新为新 parent 的左孩子（child = 2parent + 1），继续循环。 小根堆的向下调整

/**
 * 小根堆的向下调整
 * @param array 待调整的数组
 * @param parent 需要调整的节点索引
 */
public void shiftDown(int[] array, int parent) {
    // child先标记parent的左孩子，因为parent可能有左没有右
    int child = 2 * parent + 1;
    int size = array.length;
//如果右孩子不存在，那直接标记他，不会执行if有孩子的这一部分
    while (child < size) {
        // 如果右孩子存在，找到左右孩子中较小的孩子，用child进行标记
        if (child + 1 < size && array[child + 1] < array[child]) {
            child += 1;
        }

        // 如果双亲比其最小的孩子还小，说明该结构已经满足堆的特性了
        if (array[parent] <= array[child]) {
            break;
        } else {
            // 将双亲与较小的孩子交换
            int t = array[parent];
            array[parent] = array[child];
            array[child] = t;

            // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
            parent = child;
            child = parent * 2 + 1;
        }
    }
}

大堆的向下调整：

/**
 * 大根堆的向下调整
 * @param array 待调整的数组
 * @param parent 需要调整的节点索引
 */
public void shiftDownMax(int[] array, int parent) {
    int child = 2 * parent + 1; // 先标记左孩子（完全二叉树中左孩子优先存在）
    int size = array.length;

    while (child < size) { // 左孩子存在时才需要调整
        // 若右孩子存在，且右孩子的值 > 左孩子的值，则child标记右孩子（找更大的孩子）
        if (child + 1 < size && array[child + 1] > array[child]) {
            child++;
        }

        // 若父节点的值 >= 最大孩子的值，满足大根堆，退出
        if (array[parent] >= array[child]) {
            break;
        } else {
            // 交换父节点与最大孩子（将大值上移）
            int temp = array[parent];
            array[parent] = array[child];
            array[child] = temp;

            // 继续向下调整：父节点移到child位置，child更新为新父节点的左孩子
            parent = child;
            child = 2 * parent + 1;
        }
    }
}

大根堆的向下调整逻辑与小根堆类似，核心区别在于：比较时需找到左右孩子中值更大的那个，并确保父节点的值大于等于孩子节点的值。 向上调整 核心逻辑：新元素从底层向上比较，若不满足堆的父子关系（如大根堆中子节点大于父节点），则与父节点交换，直到找到合适位置或成为根节点。 大根堆的向上调整的步骤

新元素插入到堆的末尾（数组最后一个位置），记为 child（子节点索引）。
计算其父节点索引 parent = (child - 1) / 2。
比较 child 与 parent 的值：
若 child 的值 > parent 的值（大根堆不满足）：交换两者，child 指向原 parent 的位置，重复步骤 2~3。
若 child 的值 ≤ parent 的值（满足大根堆）：调整结束。

/**
 * 大根堆的向上调整（插入新元素后）
 * @param array 堆的数组
 * @param child 新元素的索引（初始为数组末尾）
 */
public void shiftUp(int[] array, int child) {
    int parent = (child - 1) / 2; // 计算父节点索引
    while (child > 0) { // 子节点不是根节点时继续
        // 大根堆：若子节点 > 父节点，交换
        if (array[child] > array[parent]) {
            int temp = array[child];
            array[child] = array[parent];
            array[parent] = temp;
            // 向上移动：子节点指向父节点，重新计算父节点
            child = parent;
            parent = (child - 1) / 2;
        } else {
            // 满足大根堆性质，退出
            break;
        }
    }
}

小根堆的向上调整 小根堆的向上调整只需将 “子节点> 父节点” 改为 “子节点 < 父节点”：

public void shiftUpMin(int[] array, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {
        // 小根堆：若子节点 < 父节点，交换
        if (array[child] < array[parent]) {
            int temp = array[child];
            array[child] = array[parent];
            array[parent] = temp;
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

插入与删除

堆的插入 堆的插入总共需要两个步骤：先将元素放入到底层空间中（注意：空间不够时需要扩容）将最后新插入的节点向上调整，直到满足堆的性质

比如我要插入80这个这个值，使用大堆的向上调整方法

import java.util.Arrays;

public class MaxHeap {
    private int[] elem;
    private int usedSize;

    public MaxHeap() {
        this.elem = new int[10]; 
        this.usedSize = 0;
    }

    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[usedSize] = val;
        siftUp(usedSize);
        usedSize++;
    }

    private void siftUp(int child) {
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    private void swap(int i, int j) {
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp;
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    // 测试方法
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();
        maxHeap.offer(10);
        maxHeap.offer(20);
        maxHeap.offer(5);
        maxHeap.offer(30);
        // 此时堆中元素应满足大根堆性质，根节点为30
        for (int i = 0; i < maxHeap.usedSize; i++) {
            System.out.print(maxHeap.elem[i] + " ");
        }
    }
}

小堆插入向上调整的方法 就是比较的大小不一样

/**
 * 小根堆的向上调整（用于插入新元素后恢复堆性质）
 * @param array 存储堆的数组
 * @param child 新插入元素的索引（初始为数组末尾）
 */
public void shiftUpMin(int[] array, int child) {
    // 计算父节点索引
    int parent = (child - 1) / 2;
    
    // 循环条件：子节点不是根节点（child > 0）
    while (child > 0) {
        // 小根堆：若子节点 < 父节点，说明不满足堆性质，需要交换
        if (array[child] < array[parent]) {
            // 交换子节点与父节点
            int temp = array[child];
            array[child] = array[parent];
            array[parent] = temp;
            
            // 向上移动：子节点指向原父节点位置，重新计算父节点
            child = parent;
            parent = (child - 1) / 2;
        } else {
            // 子节点 >= 父节点，满足小根堆性质，退出调整
            break;
        }
    }
}

// 小根堆插入元素的完整方法（包含扩容判断）
public void insertMinHeap(int[] array, int value, int size) {
    // 假设array容量足够，直接插入到末尾（实际需判断扩容）
    array[size] = value;
    // 对新插入的元素执行向上调整
    shiftUpMin(array, size);
}

堆的删除 堆的删除操作通常指删除堆顶元素（大根堆的最大值或小根堆的最小值） 核心逻辑是通过 “覆盖堆顶 + 向下调整” 来恢复堆的性质，具体步骤：

堆删除的完整逻辑（以大根堆为例）

判断堆是否为空：若堆中无元素，直接返回（或抛出异常）。

用最后一个元素覆盖堆顶：

将堆的最后一个元素（数组末尾元素）赋值给堆顶（索引 0），然后删除最后一个元素（有效长度减 1）。（目的：快速移除堆顶，同时避免堆结构断裂）。从堆顶执行向下调整：
由于新堆顶可能破坏堆的性质（如大根堆中，新堆顶的值可能小于子节点），需对新堆顶执行向下调整，使其与子节点比较并交换，直到整个堆重新满足性质。

就是换完就是这个效果，而且也不是彻底删除，只是最后一个和堆顶的元素交换了位置，然后进行将有效usedSize 进行-1 ，对他覆盖。

   private void shiftDown(int parent, int len) {
        int child = 2 * parent + 1;
        while (child < len) {
            // 找左右孩子中更大的那个
            if (child + 1 < len && elem[child + 1] > elem[child]) {
                child++;
            }
            // 父节点 >= 最大子节点，满足堆性质
            if (elem[parent] >= elem[child]) {
                break;
            }
            // 交换并继续调整
            swap(parent, child);
            parent = child;
            child = 2 * parent + 1;
        }
    }
    private void swap(int i, int j) {
        int temp = elem[i];
        elem[i] = elem[j];
        elem[j] = temp;
    }

    // 堆的删除操作（删除堆顶元素）
    public int remove() {
    //当然这里也可以再写一个判断是否为空的方法
        if (usedSize == 0) {
            throw new RuntimeException("堆为空，无法删除");
        }
        // 1. 保存堆顶元素（要返回的值）
        int top = elem[0];
        // 2. 用最后一个元素覆盖堆顶
        elem[0] = elem[usedSize - 1];
        usedSize--; 
        // 有效长度减1（逻辑删除最后一个元素）
     
        // 从堆顶进行向下调整，恢复堆性质
        shiftDown(0, usedSize);
        return top;
    }
}

用堆模拟实现优先级队列

import java.util.Arrays;

public class TestHeap {

    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    public void initArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    /**
     * 创建大根堆
     * 向下调整的方式：时间复杂度：O(N)
     */
    public void createHeap() {
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            siftDown(parent,usedSize);
        }
    }
    /**
     * 向下调整的方法
     * @param parent 每棵子树的根节点下标
     * @param usedSize 每棵子树是否调整结束的位置
     */
    private void siftDown(int parent, int usedSize) {
        int child = 2 * parent + 1;
        //说明 至少有一个左孩子
        //至少有一个左孩子
        //elem[child + 1]这里可能会产生child + 1 的空
//             if(elem[child] < elem[child + 1]){
//                 child++;
//             }

        while (child < usedSize) {
            if(child+1 < usedSize && elem[child] < elem[child+1]) {
                child++;
            }
            //代码走到这里 表示 child下标 一定是最大孩子的下标
            if(elem[child] > elem[parent]) {
                //交换
                swap(child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    private void swap(int i,int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    /**
     * 插入元素
     * @param val
     */
    public void offer(int val) {
        if(isFull()) {
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        //向上 调整
        siftUp(usedSize);
        usedSize++;
    }

    /**
     * 向上调整
     * @param child
     */
    private void siftUp(int child) {
        int parent = (child-1)/2;
        while (parent >= 0) {
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }

    /**
     * 删除的逻辑
     * @return
     */
    public int poll() {
        if(isEmpty()) {
            return -1;
        }
        int val = elem[0];
        swap(0,usedSize-1);
        usedSize--;
        siftDown(0,usedSize);
        return val;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 获取优先级队列 堆顶元素
     * @return
     */
    public int peek() {
        if(isEmpty()) {
            return -1;
        }
        return elem[0];
    }

    //O(n*logN)
    public void heapSort() {
        int end = usedSize-1;
        while (end > 0) {
            swap(0,end);
            siftDown(0,end);
            end--;
        }
    }

}

//Test
import java.util.Comparator;
import java.util.PriorityQueue;

class Student implements Comparable<Student>{
    public int age;

    public Student(int age) {
        this.age = age;
    }

    @Override
    public int compareTo(Student o) {
        //return this.age - o.age;
        return o.age - this.age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "age=" + age +
                '}';
    }
}

class ImpMaxComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        //return o1.compareTo(o2);
        return o2.compareTo(o1);
    }
}

class ImpMinComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
        return o1.compareTo(o2);
    }
}

public class Test {


    public int[] smallestK(int[] array, int k) {
        if(array == null || k <= 0) {
            return null;
        }
        ImpMaxComparator impMaxComparator = new ImpMaxComparator();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(impMaxComparator);

        //1,把前K个元素 创建成 大根堆
        for(int i = 0;i < k;i++) {
            priorityQueue.offer(array[i]);
        }
        //遍历剩下的N-K个元素
        for (int i = k; i < array.length; i++) {
            int peekVal = priorityQueue.peek();
            if(peekVal > array[i]) {
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }





    public static void main(String[] args) {
        ImpMaxComparator impMaxComparator = new ImpMaxComparator();
        ImpMinComparator impMinComparator = new ImpMinComparator();

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(impMinComparator);
        priorityQueue.offer(12);
        priorityQueue.offer(5);
        priorityQueue.offer(9);
        priorityQueue.offer(100);

        System.out.println(priorityQueue.peek());

 /*
        PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>();
        priorityQueue2.offer(new Student(12));
        priorityQueue2.offer(new Student(5));

        System.out.println(priorityQueue2.peek());
*/
    }
    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {27,15,19,18,28,34,65,49,25,37};
        testHeap.initArray(array);

        testHeap.createHeap();

        testHeap.heapSort();

        /*for (int i = 0; i < array.length; i++) {
            testHeap.offer(array[i]);
        }*/

        //System.out.println(testHeap.poll());//65
    }

}

注意：堆的删除⼀定删除的是堆顶元素。具体如下： 1.将堆顶元素对堆中最后⼀个元素交换 2.将堆中有效数据个数减少⼀个 3.对堆顶元素进行向下调整

堆的应用

二、堆的应用 1、PriorityQueue的实现用堆作为底层结构封装优先级队列

2、堆排序堆排序即利用堆的思想来进行排序，总共分为两个步骤：

（1）建堆：升序（从小到大）：创建大堆降序（从大到小）：创建小堆

（2）利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

3、Top-k问题 TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

（1）用数据集合中前K个元素来建堆

前k个最大的元素，则建小堆

前k个最小的元素，则建大堆

(2）用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

    将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

地址：https://leetcode.cn/problems/smallest-k-lcci/

import java.util.Comparator;
import java.util.PriorityQueue;

public class SmallestK {

    // 自定义大根堆比较器：让大的元素优先级更高
    class ImpMaxComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1); // 反转比较逻辑，实现大根堆
        }
    }

    public int[] smallestK(int[] array, int k) {
        // 边界条件处理：数组为空或k<=0时返回空数组（而非null，更符合实际需求）
        if (array == null || array.length == 0 || k <= 0 || k > array.length) {
            return new int[0];
        }

        //创建基于大根堆的优先队列
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new ImpMaxComparator());

        //先将前k个元素放入大根堆
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(array[i]);
        }

        // 遍历剩下的n-k个元素，若当前元素比堆顶小，则替换堆顶
        for (int i = k; i < array.length; i++) {
            int peekVal = priorityQueue.peek(); // 获取堆顶（当前堆中最大的元素）
            if (peekVal > array[i]) {
                priorityQueue.poll(); // 移除堆顶
                priorityQueue.offer(array[i]); // 插入更小的元素
            }
        }

        // 步骤3：将堆中最终的k个元素取出，即为最小的k个元素
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }
    public static void main(String[] args) {
        SmallestK smallestK = new SmallestK();
        int[] array = {27, 15, 19, 10, 5, 20};
        int k = 3;
        int[] result = smallestK.smallestK(array, k);
        
    
        for (int num : result) {
            System.out.print(num + " "); 
        }
    }
}

注意：此方法只是PriorityQueue 的使用，而不是topK 的最好解决方法

优先级队列在插入元素时有个要求：插入的元素不能是null或者元素之间必须要能够进行比较，为了简单起见，我们只是插入了Integer类型，那优先级队列中能否插入自定义类型对象呢？

优先级队列底层使用堆，而向堆中插入元素时，为了满足堆的性质，必须要进行元素的比较，而此时Card是没有办法直接进行比较的，因此抛出异常。

3.常用的接口

1. PriorityQueue的特性 Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本⽂主要介绍PriorityQueue。在 Java 中使用PriorityQueue，需注意以下核心要点，已统一字体呈现： 必须导入对应包 PriorityQueue位于java.util包下，使用前必须通过import语句导入，否则会报编译错误。

import java.util.PriorityQueue;

PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
不能插入null对象，否则会抛出NullPointerException
没有容量限制，可以插入任意多个元素，其内部可以自动扩容
插入和删除元素的时间复杂度为o(log2为底N的对数)
PriorityQueue底层使用了堆数据结构
PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素

PriorityQueue常用接口介绍

优先级队列的构造此处只是列出了PriorityQueue中常见的几种构造几种： Java 中PriorityQueue（优先级队列）构造器的说明，涉及三个构造器及其功能：

PriorityQueue()：创建空的优先级队列，默认容量 11。 PriorityQueue(int initialCapacity)：创建指定初始容量的优先级队列，初始容量不能小于 1，否则抛IllegalArgumentException异常。 PriorityQueue(Collection<? extends E> c)：用一个集合来创建优先级队列。

static void TestPriorityQueue(){
 // 创建⼀个空的优先级队列，底层默认容量是11 
PriorityQueue<Integer> q1 = new PriorityQueue<>();
 // 创建⼀个空的优先级队列，底层的容量为initialCapacity 
PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
 ArrayList<Integer> list = new ArrayList<>();
 list.add(4);
 list.add(3);
 list.add(2);
 list.add(1);
 // ⽤ArrayList对象来构造⼀个优先级队列的对象
 
// q3中已经包含了三个元素
 
PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
 System.out.println(q3.size());
 System.out.println(q3.peek())

注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器

 // ⽤⼾⾃⼰定义的⽐较器：直接实现Comparator接⼝，然后重写该接⼝中的compare⽅法即可
 
class IntCmp implements Comparator<Integer>{
 @Override
 public int compare(Integer o1, Integer o2) {
 return o2-o1;
 }
 }

public class TestPriorityQueue {
 public static void main(String[] args) {
 PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
 p.offer(4);
 p.offer(3);
 p.offer(2);
 p.offer(1);
 p.offer(5);
 System.out.println(p.peek());
 }
 }

此时创建出来的就是⼀个大堆。 插入/删除/获取优先级最高的元素 Java 中PriorityQueue（优先级队列）常用方法的说明，涉及六个方法及其功能：

boolean offer(E e)：插入元素 e，插入成功返回 true；若 e 为 null，抛NullPointerException异常；空间不足时会扩容，时间复杂度为 O (log n)。
E peek()：获取优先级最高的元素，队列为空返回 null。
E poll()：移除并返回优先级最高的元素，队列为空返回 null。
int size()：获取有效元素的个数。
void clear()：清空队列。
boolean isEmpty()：检测队列是否为空，空返回 true。

static void TestPriorityQueue2(){
 int[] arr = {4,1,9,2,8,0,7,3,6,5};
 // ⼀般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
 
// 否则在插⼊时需要不多的扩容
 
// 扩容机制：开辟更⼤的空间，拷⻉元素，这样效率会⽐较低
 
PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
 for (int e: arr) {
 q.offer(e);
 }
 System.out.println(q.size());   // 打印优先级队列中有效元素个数
 
System.out.println(q.peek());   // 获取优先级最⾼的元素
 
    // 从优先级队列中删除两个元素之和，再次获取优先级最⾼的元素
 
    q.poll();
    q.poll();
    System.out.println(q.size());   // 打印优先级队列中有效元素个数
 
    System.out.println(q.peek());   // 获取优先级最⾼的元素
 
    q.offer(0);
    System.out.println(q.peek());   // 获取优先级最⾼的元素
 
    // 将优先级队列中的有效元素删除掉，检测其是否为空
 
    q.clear();
    if(q.isEmpty()){
        System.out.println("优先级队列已经为空!!!");
    }
    else{
        System.out.println("优先级队列不为空");
    }
 }

注意：以下是JDK1.8中，PriorityQueue的扩容方式：JDK17也是类似的，只不过部分进行了封装

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
 }
 private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;

优先级队列的扩容说明： • 如果容量小于64时，是按照oldCapacity的2倍方式扩容的 • 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的 • 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

比较器的问题

这时候你要思考一个问题，观察下面代码：

   public static void main(String[] args) {
        PriorityQueue<Student> priorityQueue2 = new PriorityQueue<>();
        priorityQueue2.offer(new Student());
    }

此时运行会报错：类型转换异常

因为是一个自定义类型，跟根节点比较，你是自定义类型，跟什么比，插入进去要能比较大小，所以要借助比较器或者compable接口

那为什么Integer为什么可以呢？是因为他是包装类型，他是实现了comparable,本身就可以比较大小，这是他的源码

看到图上的源码其实调用的都是下面的因为this()调用本类中其他构造方法

那我们上面不带参数的构造方法和带一个参数的构造方法（传容量的）都不能指定比较器，是没有传比较器的所以比较器是值为null;

还有只有一个比较器的参数的构造方法，看下面的方法

那他的默认小堆是怎么创建的呢，答案再offer里

点击siftUp，上半边是siftUp

走完这个代码就成小根堆了

方法void siftUp(int k, E x)用于在插入元素后，将元素从位置k向上调整，以维护堆的性质
它会根据是否有自定义比较器（comparator），选择调用shiftUpUsingComparator（用比较器比较）或shiftUpComparable（用元素自身的Comparable接口比较）。
在shiftUpComparable方法中，通过不断与父节点比较（父节点索引为(k - 1) >>> 1），若当前元素优先级更高（如更小），则交换位置，直到元素放到正确位置，确保堆的结构（如小顶堆）符合预期。 <<（左移）：左移 1 位，数值乘以 2；左移 n 位，数值乘以 2 的n次方（不溢出时） >>（右移）：右移 1 位，数值除以 2；右移 n 位，数值除以 2 的n次方（不溢出时）

（无符号右移）：右移 1 位，数值除以 2（取整）；右移 n 位，数值除以 (2^n)（取整）。 左移（<<）：乘 2 的 n 次幂，补 0。 带符号右移（>>）：除 2 的 n 次幂，符号位补自身。 无符号右移（>>>）：除 2 的 n 次幂，高位补 0（结果非负）。

compareTo方法：决定了“谁更大”的规则 key是上一个存的值，e 存的是当前值

return this.age - o.age; this 小则返回负数 --> 小根堆（小元素优先）
return o.age - this.age; this 小则返回正数 --> 大根堆 (大元素优先) compareTo方法是Comparable接口的核心，作用是定义当前对象（this）与参数对象（o）的 “大小关系”，返回值仅通过 “正负” 传递关键信息，绝对值无意义：
返回负数：表示this < o（当前对象 “小于” 参数对象）
返回0：表示this == o（两者 “相等”，优先级一致）
返回正数：表示this > o（当前对象 “大于” 参数对象）

例子：当 compareTo 定义为 return this.age - o.age 时，key.compareTo((T) e) >= 0 的语义是 “当前元素（key）的年龄 ≥ 父节点（e）的年龄”。若 key.age < e.age，compareTo 返回负数，不满足 >= 0，则进入循环：将父节点 e 下移到当前 k 位置，然后 k 移动到父节点索引，继续向上比较。若 key.age >= e.age，compareTo 返回非负数，满足 >= 0，则 break 循环，将 key 放到当前 k 位置。 小根堆： return this.age - o.age

当 compareTo 方法写为 return this.age - o.age 时，我们通过“年龄差”来体现“大小关系”：

场景1： this.age < o.age 根据 compareTo 语义，这表示 this < o （当前对象比参数对象“小”）。比如 this.age = 5 ， o.age = 12 ，则 this.age - o.age = 5 - 12 = -7 （负数）。
场景2： this.age > o.age 根据compareTo 语义，这表示 this > o （当前对象比参数对象“大”）。

比如 this.age = 12 ， o.age = 5 ，则 this.age - o.age = 12 - 5 = 7 （正数）。

优先队列（默认基于小根堆实现）的规则：堆顶始终是“最小的元素”。 当元素插入/调整时，优先队列会用 compareTo 判断“谁更小”，并把更小的元素往上调整到堆顶。

若 this < o （返回负数），则 this 更“小”，（return this.age - o.age）会被优先放到堆顶。
最终堆顶是所有元素中年龄最小的元素，即“小根堆”。

大根堆： return o.age - this.age 当 compareTo 改为 return o.age - this.age 时，“年龄差”的语义完全反转了：

场景1： this.age < o.age 比如 this.age = 5 ， o.age = 12 ，则 o.age - this.age = 12 - 5 = 7 （正数）。根据 compareTo 语义，这表示 this > o （当前对象比参数对象“大”）。
场景2： this.age > o.age 比如 this.age = 12 ， o.age = 5 ，则 o.age - this.age = 5 - 12 = -7 （负数）。根据语义，这表示 this < o （当前对象比参数对象“小”）。
优先队列的大根堆逻辑

优先队列的规则变成：堆顶始终是“最大的元素”。当元素插入/调整时，优先队列会用 compareTo 判断“谁更大”，并把更大的元素往上调整到堆顶。

若 this > o （返回正数），则 this 更“大”，会被优先放到堆顶。
最终堆顶是所有元素中年龄最大的元素，即“大根堆”。

compareTo 的返回值直接决定了“大小比较的规则”，而优先队列（堆）会根据这个规则，自动维护“堆顶是最小/最大元素”的特性：

return this.age - o.age → 小的元素返回负数 → 小根堆（堆顶最小）。
return o.age - this.age → 大的元素返回正数 → 大根堆（堆顶最大）。

本质是通过反转“年龄差的计算顺序”，让 compareTo 对“大小”的判定逻辑完全反过来，从而改变堆的类型。

注意：这里我用的是comparable方法，Integer的代码我修改不了，如果你想用大根堆，我改不了他的源码，所以只能用比较器。如果是下面这种自定义类型的话，虽然可以改comparable但是也不是很方便，如果你改了，这段时间所有人按着这个写的代码都要被修改，，就不是很方便了。

比较器实现大小堆的转换代码如下：

//比较器大根堆
class ImpMaxComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
     // 等价于 return o2 - o1（对Integer而言）
        return o2.compareTo(o1);
    }
}
//小根堆
class ImpMinComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer o1, Integer o2) {
     // 等价于 return o1 - o2（对Integer而言）
        return o1.compareTo(o2);
    }
}
public static void main(String[] args) {
        ImpMaxComparator impMaxComparator = new ImpMaxComparator();
        ImpMinComparator impMinComparator = new ImpMinComparator();

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(impMinComparator);
        priorityQueue.offer(12);
        priorityQueue.offer(5);
        priorityQueue.offer(9);
        priorityQueue.offer(100);

        System.out.println(priorityQueue.peek());

compareTo方法：决定了“谁更大”的规则