堆就像堆积木 —— 大根堆和小根堆入门

你有没有遇到过这样的场景：老师把全班同学的考试分数混在一起，你需要最快找出最高分；或者你在超市排队结账，想知道排在自己前面的人还有多少位？生活中经常需要“快速找到最大或最小的那个”，这就是堆（Heap）的用武之地。

堆是一种特殊的数据结构，它像一个有规则的“积木塔”：最大的积木永远在最上面（大根堆），或者最小的积木在最上面（小根堆）。你每次从塔顶拿走积木，就能立刻得到最大或最小的那个。而且，当有新积木加入时，堆会自动调整，让新积木“飘”到合适的位置。今天我们就来认识堆的概念、性质，并亲手用代码实现一个简单的堆。

堆是什么？用生活中的例子理解

从整理书包说起

你有一堆大小不一的玩具，想最快拿到最大的那个玩具。你会怎么做？是把所有玩具挨个比一遍，还是把最大的玩具放在最容易被拿到的地方？显然，你会把最大的玩具放在最上面。在计算机里，我们经常需要从一堆数据中快速找出最大（或最小）的那个，并且还会不断地加入新数据、取出数据。这种场景下，堆就是一种非常高效的数据结构。

堆可以想象成一个“有规则”的堆积木：所有的积木按照大小排列，最大的积木永远在最上面（或者最小的在最上面）。这样你每次拿取最上面的积木，就能得到最大（或最小）的。但是堆不是完全排好序的，它只保证父节点比子节点大（或小）的规则，所以它比完全排序要快得多。

堆的另一个例子：食堂取餐号

食堂取餐时，每个窗口都有一个取号机。你拿到的号码越小，就越早吃到饭。如果食堂用一个小根堆来管理等待的号码，那么窗口叫号时，就直接取出堆顶的最小号，效率极高。相反，如果是一个“加急窗口”，需要优先处理号码最大的客人（比如VIP），那就用大根堆。

堆的数据结构原理

堆是一种特殊的完全二叉树，它满足以下两个性质：

结构性质：堆是一棵完全二叉树。完全二叉树是指除了最后一层，其他层都是满的，并且最后一层的节点都尽量靠左排列。也就是说，你在构建堆时，节点会先填满左边，不会出现“右边有节点而左边空缺”的情况。
堆序性质：对于大根堆（Max Heap），任何父节点的值都大于或等于它的子节点；对于小根堆（Min Heap），任何父节点的值都小于或等于它的子节点。

大根堆的根节点是整个堆中的最大值，小根堆的根节点是整个堆中的最小值。

我们用ASCII图来展示一个大根堆和小根堆的例子。

注意观察：大根堆中每个父节点都比子节点大，但不要求左右子节点之间的大小顺序（比如9和8，谁左谁右无所谓）。小根堆类似。

堆的存储方式：用数组“藏”一棵树

因为堆是完全二叉树，我们可以用一个数组来存储它，不需要用指针连接节点。数组的下标习惯从0开始（很多编程语言如C++、Python的数组从0开始），但也可以从1开始。这里我们统一使用从0开始的方式。

对于下标为 i 的节点：

左孩子下标 = 2 * i + 1
右孩子下标 = 2 * i + 2
父节点下标 = (i - 1) // 2（整数除法）

如果从1开始，公式是：左孩子 2*i，右孩子 2*i+1，父节点 i//2。两种都可以，但要记得下标含义不同。

用数组存储堆的好处是节省空间，且能通过简单的下标计算访问父子节点。

堆的核心操作：上浮与下沉

堆最核心的操作是 上浮（sift up） 和 下沉（sift down），它们用于维护堆序性质。

上浮（Sift Up）

当你往堆里插入一个新元素时，首先把它放到数组的末尾（也就是完全二叉树的最后一个位置）。然后，让它不断与父节点比较：如果它比父节点大（对于大根堆）或小（对于小根堆），就和父节点交换位置，直到它不再大于（或小于）父节点为止。这个过程就像气泡从水中往上冒，所以叫“上浮”。

生活中的例子：你在排队时，一个比你高的人（大根堆）插到你前面，你觉得不公平，就和前面的人交换位置，直到你前面的人都比你矮。这样最高的人就到了最前面。

下沉（Sift Down）

当你取出堆顶元素时（比如取最大值或最小值），堆顶就空缺了。为了保持完全二叉树结构，我们把数组的最后一个元素移动到堆顶，然后让它不断与它的子节点比较：如果是大根堆，就与较大的子节点交换；如果是小根堆，就与较小的子节点交换。直到它不再比子节点小（或大）为止。这个过程像石头往下沉，所以叫“下沉”。

生活中的例子：你拿走塔顶最大的积木后，从塔底随便拿一块积木放在塔顶，然后看它比下面的哪块积木小，就不断往下掉，直到找到合适的位置。

从零开始实现一个小根堆

下面我们用 C++ 和 Python 分别实现一个小根堆类，包含插入、获取最小值、删除最小值操作。代码中每行变量定义都写中文注释，方便理解。

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm> // 用于swap
using namespace std;

// 小根堆类
class MinHeap {
private:
    vector<int> heap; // 存储堆元素的动态数组

    // 上浮操作：用于插入后调整
    void siftUp(int index) {
        // 当节点不是根节点，并且比父节点小（小根堆），则交换
        while (index > 0) {
            int parent = (index - 1) / 2; // 父节点下标
            if (heap[index] < heap[parent]) {
                swap(heap[index], heap[parent]); // 交换当前节点与父节点
                index = parent; // 继续向上调整
            } else {
                break; // 已经满足堆序，停止
            }
        }
    }

    // 下沉操作：用于删除根后调整
    void siftDown(int index) {
        int size = heap.size();
        while (true) {
            int left = 2 * index + 1;  // 左孩子下标
            int right = 2 * index + 2; // 右孩子下标
            int smallest = index;      // 先假设当前节点是最小的

            // 在三个节点（当前、左、右）中找到最小的那个
            if (left < size && heap[left] < heap[smallest]) {
                smallest = left;
            }
            if (right < size && heap[right] < heap[smallest]) {
                smallest = right;
            }

            if (smallest != index) {
                swap(heap[index], heap[smallest]); // 把最小的换到当前节点
                index = smallest; // 继续向下调整
            } else {
                break; // 已经满足堆序，停止
            }
        }
    }

public:
    // 插入一个元素
    void push(int val) {
        heap.push_back(val);       // 先把新元素加到数组末尾
        siftUp(heap.size() - 1);   // 然后从该位置开始上浮
    }

    // 获取堆顶元素（最小值）
    int top() {
        if (heap.empty()) {
            throw runtime_error("Heap is empty");
        }
        return heap[0]; // 根节点就是最小值
    }

    // 删除堆顶元素
    void pop() {
        if (heap.empty()) {
            throw runtime_error("Heap is empty");
        }
        // 把数组最后一个元素搬到堆顶，再删除最后一个元素
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) {
            siftDown(0); // 从根节点开始下沉调整
        }
    }

    // 返回堆的大小
    int size() {
        return heap.size();
    }

    // 判断堆是否为空
    bool empty() {
        return heap.empty();
    }
};

// 测试代码
int main() {
    MinHeap h;           // 创建一个小根堆
    h.push(5);           // 依次插入数字
    h.push(3);
    h.push(8);
    h.push(1);
    h.push(9);
    h.push(2);

    cout << "小根堆依次取出最小值: ";
    while (!h.empty()) {
        cout << h.top() << " ";  // 输出当前最小值
        h.pop();                 // 删除最小值
    }
    cout << endl;
    // 输出应为: 1 2 3 5 8 9
    return 0;
}

Python 实现

class MinHeap:
    def __init__(self):
        self.heap = []  # 列表存储堆元素

    def _sift_up(self, index):
        """上浮操作：插入后使用"""
        while index > 0:
            parent = (index - 1) // 2  # 父节点下标
            if self.heap[index] < self.heap[parent]:
                # 如果当前节点比父节点小，交换
                self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
                index = parent  # 继续向上
            else:
                break

    def _sift_down(self, index):
        """下沉操作：删除根后使用"""
        size = len(self.heap)
        while True:
            left = 2 * index + 1   # 左孩子下标
            right = 2 * index + 2  # 右孩子下标
            smallest = index       # 先假设当前节点最小

            # 找到三个节点中最小的那个
            if left < size and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < size and self.heap[right] < self.heap[smallest]:
                smallest = right

            if smallest != index:
                # 如果最小的不是当前节点，则交换
                self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
                index = smallest  # 继续向下
            else:
                break

    def push(self, val):
        """插入一个元素"""
        self.heap.append(val)            # 先加到最后
        self._sift_up(len(self.heap) - 1)  # 再上浮

    def top(self):
        """获取堆顶元素（最小值）"""
        if not self.heap:
            raise Exception("Heap is empty")
        return self.heap[0]

    def pop(self):
        """删除堆顶元素"""
        if not self.heap:
            raise Exception("Heap is empty")
        # 将最后一个元素移到堆顶，然后删除最后一个
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        if self.heap:
            self._sift_down(0)

    def size(self):
        return len(self.heap)

    def empty(self):
        return len(self.heap) == 0


# 测试
h = MinHeap()
h.push(5)
h.push(3)
h.push(8)
h.push(1)
h.push(9)
h.push(2)

print("小根堆依次取出最小值: ", end="")
while not h.empty():
    print(h.top(), end=" ")
    h.pop()
print()
# 输出: 1 2 3 5 8 9

如何改成大根堆？

要让上面的代码变成大根堆很简单，只需要把所有比较符号反过来：

上浮时：如果当前节点比父节点大则交换。
下沉时：找三个节点中最大的那个，如果当前节点比它小则交换。

或者更简单的方法：存入数据时取负数，这样小根堆就变成了大根堆（因为负数的最小值对应原数的最大值）。取出时再取回负数即可。但这只是一种技巧，并不改变堆本身的定义。

上浮时，当 index > 0 才需要继续，因为根节点没有父节点。
下沉时，要确保 left < size 和 right < size 再取孩子，否则数组越界。
pop() 时，如果堆只有一个元素，直接移除即可，不需要下沉；如果堆为空，要抛出异常或做保护。

4. 认为堆是完全有序的

堆只保证根节点是最大或最小，但不保证整个树有序。例如大根堆中，左子节点可能比右子节点小，这是允许的。如果你需要完全排序，应该用堆排序，但那是在堆的基础上进行额外操作。

完整可运行示例

上面的 C++ 和 Python 代码都是完整可运行的。你可以直接复制到自己的编辑器中运行看看。

C++：编译运行后输出 1 2 3 5 8 9，表示依次取出最小值，顺序正确。 Python：运行后输出相同的结果。

如果你想测试大根堆，可以把比较符号取反，或者参考“改成大根堆”的方法。

总结与拓展

堆是一种完全二叉树，用数组存储，效率高。
大根堆根节点最大，小根堆根节点最小。
核心操作：上浮（插入时使用）、下沉（删除时使用），时间复杂度都是 O(log n)。
堆常用于实现优先队列（例如C++的 priority_queue，Python的 heapq 模块），以及堆排序。

现在你已经掌握了堆的基本概念和简单实现！接下来可以学习：

[上浮和下沉操作的详细图解与复杂度分析]
[用堆实现优先队列]
[堆排序算法]
[常见面试题：合并K个有序链表、数据流中的中位数]

继续加油，堆是一个很有用的工具，在很多算法竞赛和实际开发中都会用到。

堆的概念与性质（大根堆、小根堆）