特殊的完全二叉树-堆

数据结构 • Dec 8, 2024

前言

堆（Heap）是一种非常重要且常用的数据结构，广泛应用于任务调度、优先队列、图算法等领域。尽管堆在很多编程语言中都有实现，但它的基本原理和应用常常让人感到困惑。在本文中，我们将深入探讨堆的定义、实现原理及其应用，另外使用Java手写一个堆实现，以及介绍c++和Java库中自带的堆实现。

什么是堆？

堆是一种特殊的完全二叉树（Complete Binary Tree），在这棵树中，节点的值满足特定的顺序要求。常见的堆有两种类型：

最大堆（Max-Heap）：每个父节点的值都大于或等于其子节点的值，堆顶是树中最大值。
最小堆（Min-Heap）：每个父节点的值都小于或等于其子节点的值，堆顶是树中最小值。

堆的基本特点

完全二叉树：堆是一棵完全二叉树，这意味着除了最底层外，其他层的节点都是满的，且所有节点都靠左对齐。
堆序性：堆的每个父节点都与其子节点有一个特定的大小关系。对于最大堆，父节点的值大于或等于其子节点的值；对于最小堆，父节点的值小于或等于其子节点的值。每个节点都在以该节点为根节点的子树中，拥有最高优先级。
数组存储：堆通常使用数组来存储，树形结构通过数组索引的关系来维护父子节点关系。
ps：二叉树是可以通过数组进行实现的。一般对于满二叉树和完全二叉树，他们的父子节点之间的关系是可以通过数组的索引来表示的。对于节点k来说，它的左孩子的索引就是2k+1，它的右孩子的索引就是2k+2。所以使用数组这种数据结构来实现完全二叉树简单，而且查询效率高。

为什么需要堆这种数据结构

排序问题：

排序是计算机科学中的一个经典问题，各种排序算法（如插入排序、冒泡排序、归并排序和快速排序）都在不断改进中，旨在提高排序的效率。
在这些排序算法中，比较排序通常会有 O(n log n) 的时间复杂度，但仍然需要考虑算法在处理大规模数据时的空间复杂度和时间复杂度。
堆排序通过利用堆这一数据结构，能够在原地进行排序，不需要额外的存储空间，同时保证了 O(n log n) 的时间复杂度。

优先队列：

在计算机科学中，优先队列是一种特别的数据结构，它支持在常数时间内返回最大值或最小值（根据需求），并且支持高效地插入元素。
在实现优先队列时，通常需要进行频繁的插入、删除最大/最小元素操作。堆是最适合的实现方式之一，能够在 O(log n) 的时间内执行这些操作。

其他数据结构的限制：

尽管已有其他数据结构如平衡二叉树和排序数组能够处理类似问题，但这些结构要么实现复杂，要么空间复杂度较高。
在当时，数据存储和内存的限制促使计算机科学家寻找既能高效操作、又能节省空间的解决方案。

总结：堆适合大数据量的动态插入，删除，查询极值问题。

详细示意图

通过一个最大堆（大根堆，大顶堆）示意图建立下脑海中堆的样子。

树形结构：

数组存储：

[30, 20, 15, 10, 5]

堆的重要操作

堆的构建有两个重要的操作

上浮操作（Heapify-up）：

当一个新元素插入到堆中时，它可能不符合堆的性质，需要通过上浮操作将其移动到合适的位置。
时间复杂度：O(log n)，因为在最坏情况下，元素可能需要上浮到根节点。

下沉操作（Heapify-down）：

当堆顶元素被删除或替换时，需要通过下沉操作将堆恢复到合适的位置。
时间复杂度：O(log n)，因为在最坏情况下，堆顶元素可能需要下沉到叶节点。

堆的基本操作

创建堆：

可以通过将元素逐个插入堆中，然后通过上浮操作来构建堆。
时间复杂度：O(n log n)，其中 n 是元素的数量。

插入操作（插入新元素）：

将元素添加到堆的末尾，然后通过“上浮”（heapify-up）操作将其移动到合适的位置，保持堆的性质。
时间复杂度：O(log n)，因为在最坏情况下，元素可能需要上浮到根节点。

删除堆顶元素（删除最大或最小元素）：

移除堆顶元素后，将堆的最后一个元素放到堆顶，然后通过“下沉”（heapify-down）操作恢复堆的性质。
时间复杂度：O(log n)，因为在最坏情况下，堆顶元素可能需要下沉到叶节点。

访问堆顶元素：

堆顶元素是最大堆中的最大值或最小堆中的最小值，可以在 O(1) 时间内访问。

堆的应用

堆常用于以下场景：

优先队列：堆是实现优先队列（Priority Queue）的理想数据结构。在优先队列中，元素按照优先级排序，优先级高的元素会被优先处理。堆的特性使得插入、删除操作都能在对数时间内完成。

堆排序：堆排序（Heap Sort）是一种利用堆实现的排序算法。通过将所有元素插入堆中，之后依次删除堆顶元素并重建堆，最终得到一个有序的序列。堆排序的时间复杂度为 O(n log n)。

图算法：在 Dijkstra 和 Prim 算法中，堆用于管理图中的节点，帮助算法高效地选择具有最小（或最大）权重的节点。

合并有序文件：多个有序流的数据可以通过堆来合并成一个有序流。面试中经常考的题目。

数据流的中位数：在处理数据流时，维护一个最大堆和一个最小堆，使得最大堆的堆顶元素小于最小堆的堆顶元素，从而可以快速找到数据流的中位数。对应题目leetcode-295。

堆的实现

在大部分语言的官方库中，都会有优先队列这个数据结构。优先队列的底层就是堆，我们可以把优先队列直接当堆使用。
下面我提供一个手写的Java版本，方便我们理解堆的各种操作。真正在项目的代码中还是使用官方库的优先队列。

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

    // 构造函数
    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    // 获取堆的父节点索引
    private int parent(int index) {
        return (index - 1) / 2;
    }

    // 获取堆的左子节点索引
    private int leftChild(int index) {
        return 2 * index + 1;
    }

    // 获取堆的右子节点索引
    private int rightChild(int index) {
        return 2 * index + 2;
    }

    // 上浮操作：保持堆的性质
    private void heapifyUp(int index) {
        while (index > 0 && heap[parent(index)] < heap[index]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    // 下沉操作：保持堆的性质
    private void heapifyDown(int index) {
        int largest = index;
        int left = leftChild(index);
        int right = rightChild(index);

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }

        if (largest != index) {
            swap(index, largest);
            heapifyDown(largest);
        }
    }

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

    // 插入新元素
    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is full");
            return;
        }
        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }

    // 删除并返回堆顶元素
    public int removeMax() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return max;
    }

    // 获取堆顶元素
    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        return heap[0];
    }

    // 堆化整个数组
    public void buildHeap(int[] arr) {
        if (arr.length > capacity) {
            System.out.println("Array is too large for the heap");
            return;
        }
        this.size = arr.length;
        this.heap = arr.clone();
        for (int i = size / 2 - 1; i >= 0; i--) {
            heapifyDown(i);
        }
    }

    // 打印堆中的所有元素
    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    // 获取堆的大小
    public int getSize() {
        return size;
    }

    // 判断堆是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);

        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(5);
        maxHeap.insert(30);
        maxHeap.insert(15);

        System.out.println("Heap after insertions:");
        maxHeap.printHeap();

        System.out.println("Max element: " + maxHeap.removeMax());
        System.out.println("Heap after removing max:");
        maxHeap.printHeap();

        System.out.println("Max element: " + maxHeap.peek());
    }
}

堆的C++ 实现

在 C++ 中，堆通常使用 std::priority_queue 类来实现。默认情况下，priority_queue 使用 最大堆 来实现优先队列。

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 创建一个最大堆的优先队列
    std::priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(5);
    maxHeap.push(15);

    // 打印并移除堆顶元素（最大元素）
    while (!maxHeap.empty()) {
        std::cout << maxHeap.top() << " ";  // 查看堆顶元素
        maxHeap.pop();  // 移除堆顶元素
    }
    return 0;
}

输出：

20 15 10 5

如果你需要最小堆，可以使用 std::greater<int> 自定义比较器：

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

堆的 Java 实现

在 Java 中，PriorityQueue 类提供了对堆的实现。PriorityQueue 默认实现的是 最小堆，可以通过自定义比较器来实现最大堆。

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个最小堆的优先队列
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 插入元素
        minHeap.offer(10);
        minHeap.offer(20);
        minHeap.offer(5);
        minHeap.offer(15);

        // 打印并移除堆顶元素（最小元素）
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
        }
    }
}

输出：

5 10 15 20

如果需要最大堆，可以使用自定义的 Comparator：

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

堆的效率分析

堆的操作主要包括插入、删除和访问堆顶元素。它们的时间复杂度如下：

插入操作（push 或 offer）：O(log n)
删除堆顶元素（pop 或 poll）：O(log n)
查看堆顶元素（top 或 peek）：O(1)

由于堆是一种完全二叉树，堆的深度是 O(log n)，因此堆化操作（上浮或下沉）的时间复杂度是对数级别的。

小结

堆是一种高效的树形数据结构，广泛应用于优先队列、排序算法、图算法等场景。无论是在 C++ 还是 Java 中，堆都可以通过容器类（如 std::priority_queue 和 PriorityQueue）方便地实现。理解堆的原理和操作，对于优化程序性能，尤其是在需要处理优先级问题时，至关重要。通过这篇文章，希望你能对堆的数据结构有更深的理解，并在实际编程中充分利用堆的优势。下一篇我们介绍树堆，一种结合了平衡二叉树和堆特性的数据结构。