大顶堆

约 1309 字大约 4 分钟

优先队列困难拼多多

2024-11-1

🕵🏽 面试评估:

大厂的算法面试不仅要求候选人对常见的数据结构熟练使用，还要求深入掌握其底层的实现原理，这道题考查对堆的底层理解，模型的构建以及代码编写能力。

📝思路分析：

要实现一个堆，我们首先要了解堆的概念。

堆是一种完全二叉树，分为大顶堆和小顶堆。

大顶堆：每个节点的值都大于或等于其子节点的值。
小顶堆：每个节点的值都小于或等于其子节点的值。

完全二叉树：在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点。

回到原题，实现一个大顶堆，使用数组作为底层数据结构，并提供以下操作：

添加元素（add）：向堆中添加一个元素。
删除堆顶元素（poll）：删除并返回堆顶元素（即最大值）。

堆的添加和删除元素的操作时间复杂度都为 O(logn), n 为堆中元素的个数。在实现这两个操作之前，我们必须先用数组建堆。我们知道堆本质上是一种特殊的完全二叉树，而二叉树的特点为从根节点出发通过子树的左右节点能访问树中的所有节点，所以建堆的核心是如何找到数组中一个元素的"左右子元素"，为了简化分析过程，我们将完全二叉树节点的值与数组索引的值匹配，0， 1， 2， 3， 4， 5 ... 从左到右逐层赋值。

不难发现，如果节点的索引为 i, 左节点的索引为 2 * i + 1, 右节点的索引为 2 * i + 2, 有了索引的规律，我们可以用数组来存储二叉树节点，可以将根节点存在索引为0的位置，根节点的左节点存在 1 的位置，根节点的右节点存在2的位置，以此类推。总结一下节点之间索引的联系：

对于堆中节点的索引与其父子节点的关系如下（假设索引从 0 开始）：

父节点索引：parentIndex = (childIndex - 1) / 2
左子节点索引：leftChildIndex = 2 * parentIndex + 1
右子节点索引：rightChildIndex = 2 * parentIndex + 2

先给出一个大顶堆的示例：

有了堆，接下来我们可以实现添加和删除操作。

添加元素（add）：
1. 将新元素添加到数组末尾。
2. 通过上浮（heapifyUp）操作，维持堆的性质。
  - 比较当前节点与父节点的值，如果当前节点大于父节点，交换两者的位置，继续向上比较，直到根节点。

删除堆顶元素（poll）：
1. 将堆顶元素（即数组的第一个元素）保存，待返回。
2. 交换数组的第一个元素与最后一个元素的位置，然后删除数组的最后一个元素。
3. 通过 下沉（heapifyDown） 操作，维持堆的性质。
  - 比较当前节点与其左右子节点的值，选择最大的子节点进行交换，继续向下比较，直到叶子节点。

💻代码：

Java

public class MaxHeap {
    // 存储堆中元素的数组
    private int[] heap;

    // 堆中元素的个数
    private int size;
    
    // 堆的指定初始容量，超出容量，add 函数里2倍扩容
    private int capacity;

    // 初始化堆，指定初始容量
    public MaxHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        size = 0;
    }

    // 添加元素
    public void add(int value) {
        // 判断是否需要扩容
        if (size == capacity) {
            capacity = capacity * 2;
            int[] newHeap = new int[capacity];
            System.arraycopy(heap, 0, newHeap, 0, size);
            heap = newHeap;
        }
        heap[size] = value;
        size++;
        heapifyUp();
    }

    // 上浮操作，维持堆的性质
    private void heapifyUp() {
        int index = size - 1;
        int parentIndex = (index - 1) / 2;
        while (parentIndex >= 0 && heap[parentIndex] < heap[index]) {
            swap(heap, parentIndex, index);
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    // 删除并返回堆顶元素
    public int poll() {
        // 判断堆中是否有元素
        if (size == 0) {
            return Integer.MIN_VALUE;
        }
        int maxValue = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown();
        return maxValue;
    }

    // 下沉操作，维持堆的性质
    private void heapifyDown() {
        int index = 0;
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        while (leftChildIndex < size) {
            // 找到左右子节点中较大的那个
            int largerChildIndex = leftChildIndex;
            if (rightChildIndex < size && heap[rightChildIndex] > heap[largerChildIndex]) {
                largerChildIndex = rightChildIndex;
            }

            // 如果当前节点大于等于最大的子节点，堆已满足性质
            if (heap[index] >= heap[largerChildIndex]) {
                break;
            }

            swap(heap, index, largerChildIndex);
            index = largerChildIndex;
            leftChildIndex = 2 * index + 1;
            rightChildIndex = 2 * index + 2;
        }
    }

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

🚵🏻复杂度分析：

时间复杂度：

add: O(logn), 上浮堆的高度，堆的高度为 O(logn)
Poll: O(logn), 下沉堆的高度层，堆的高度为 O(logn)

空间复杂度：O(n) ，存储堆中的元素, n 为堆中元素的个数

大顶堆

⭐ 题目日期：

🌳 题目描述：

🕵🏽 面试评估:

🧗难度系数：⭐️⭐️⭐️⭐️⭐️

📝思路分析：

💻代码：

🚵🏻复杂度分析：