【Java】还在死磕算法？懂“堆”与“优先级队列”，代码效率飙升

欢迎 💛点赞 🌟收藏 💫关注

🏆堆

一、🎯堆的定义

堆的概念

堆是一种特殊的完全二叉树，它通过一维数组顺序存储关键码集合K={k0，k1,k2,...,kn-1}，并遵循特定的顺序关系来定义。具体来说，若对于任意节点Ki，都满足Ki <= K2i+1 且 Ki <= K2i+2（或Ki >= K2i+2），则称这样的堆为小堆。堆分为两种类型：大根堆和小根堆：

• 小根堆：根节点的值最小，父节点的值小于或等于其子节点的值；
• 大根堆：根节点的值最大，父节点的值大于或等于其子节点的值；

堆的性质

• 堆是一个完全二叉树；
• 堆中任意节点的值总是不大于（或不小于）其父节点的值；

二、🀄️堆的构建

大堆

构建过程：

代码实现：

public class Heap {
    public int[] elem; // 存储元素的数组
    public int usedSize; // 已使用的数组大小

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

    // 初始化堆
    public void initHeap(int[] elem) {
        for (int i = 0; i < elem.length; i++) {
            this.elem[i] = elem[i];
            usedSize++;
        }
    }

    // 构建大堆，通过将父节点向下调整实现
    public void creatHeap() {
        for (int parent = (usedSize - 1) / 2; parent >= 0; parent--) {
            siftDown(parent, usedSize);
        }
    }

    public void siftDown(int parent, int usedSize) {
        int child = 2 * parent + 1;
        while (child < usedSize) {
            if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
                child++;
            }
            if (elem[child] > elem[parent]) {
                swap(elem, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

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

小堆

小堆的构建思路与大堆相似，区别在于父节点的值需要小于子节点的值。

代码实现：
```java
private void swap(int[] elem, int i, int j) {
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}

public void creatHeap2() {
for (int parent = (usedSize - 1) / 2; parent >= 0; parent--) {
siftDown2(parent, usedSize);
}
}

public void siftDown2(int parent, int usedSize) {
int child = 2 * parent + 1;
while (child < usedSize) {
if (child + 1 < usedSize && elem[child] > elem[child + 1]) {
child++;