# 堆堆（heap）是一种满足特定条件的完全二叉树，主要分为两种类型 - 小顶堆（min heap）：任意节点的值 <= 其子节点的值 - 大顶堆（max heap）：任意节点的值 >= 其子节点的值堆作为完全二叉树的一个特例，具有以下特性。 - 最底层节点靠左填充，其他层的节点都被填满。 - 我们将二叉树的根节点称为“堆顶”，将底层最靠右的节点称为“堆底”。 - 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。 # 堆的常用操作需要指出的是，许多编程语言提供的是优先队列，这是一种抽象的数据结构，定义为具有优先级排序的队列。实际上，堆通常用于实现优先队列，大顶堆相当于元素从大到小的顺序出队的优先队列。从使用角度来看，我们可以将“优先队列”和“堆”看作等价的数据结构。堆的常用操作表如下 | 方法名 | 描述 | 时间复杂度 | | --------- | -------------------------------------------- | ---------- | | push() | 元素入堆 | O(log n) | | pop() | 堆顶元素出堆 | O(log n) | | peek() | 访问堆顶元素（对于大/小顶堆分别为最大/小值） | O(1) | | size() | 获取堆的元素数量 | O(1) | | isEmpty() | 判断堆是否为空 | O(1) | ```cpp // 初始化小堆 priority_queue, greater> minHeap; // 初始化大堆 priority_queue, less> maxHeap; maxHeap.push(1); maxHeap.push(3); maxHeap.push(2); maxHeap.push(5); maxHeap.push(4); int peek = maxHeap.top(); // 5 maxHeap.pop(); // 5 maxHeap.pop(); // 4 maxHeap.pop(); // 3 maxHeap.pop(); // 2 maxHeap.pop(); // 1 int size = maxHeap.size(); bool isEmpty = maxHeap.empty(); vector input {1, 3, 2, 5, 4} priority_queue, greater> minHeap(input.begin(), input.end()); ``` ## 堆的实现下面演示的是大顶堆的创建过程，小顶堆的创建一样，只需要把判断符号从`>=`替换为`<=`。 ### 1. 堆的存储与表示堆是一种完全二叉树，因此非常适合用数组来表示。当使用数组表示二叉树时，元素代表节点的值，索引代表节点在二叉树中的位置。节点指针通过索引映射公式来实现。为了方便后续使用，将索引映射公式封装成函数 ```cpp /* 获取左子节点的索引 */ int left(int i) { return 2 * i + 1; } /* 获取右子节点树 */ int right(int i) { return 2 * i + 2; } /* 获取父节点的索引 */ int parent(int i) { return (i - 1) / 2; } ``` ### 2. 访问堆顶元素堆顶元素即为二叉树的根节点，也就是列表的首个元素 ```cpp int peek() { return maxHeap[0]; } ``` ### 3. 元素入堆 ```cpp /* 元素入堆 */ void push(int val) { maxHeap.push.back(val); siftUp(size() - 1); } /* 从节点 i 开始, 从底至顶堆化 */ void siftUp(int i) { for(;;) { int p = parent(i); if (p < 0 || maxHeap[i] <= maxHeap[p]) break swap(maxHeap[i], maxHeap[p]) i = p; } } ``` ### 4. 堆顶元素出堆 ```cpp void pop() { if (isEmpty()) { throw out_of_range("堆为空"); } swap(maxHeap[0], maxHeap[size() - 1]); maxHeap.pop_back(); siftDown(0); } void siftDown(int i) { while(true) { int l = left(i), r = right(i), ma = i; if (l < size() && maxHeap[l] > maxHeap[ma]) ma = l; if (r < size() && maxHeap[r] > maxHeap[ma]) ma = r; if (ma == i) break; swap(maxHeap[i], maxHeap[ma]) i = ma; } } ``` # 建堆操作将一个列表转换成堆，这被称之为“建堆操作”。建立堆可以将原列表原封不动的添加进堆中，在进行倒叙遍历，在对每个“从顶制底堆化” ```cpp MaxHeap(vector nums) { maxHeap = nums; for (int i = parent(size() - 1); i >= 0; i--) { siftDown(i); } } ```