数据结构——堆，堆排序

前提

我们都知道内存分布中的堆区(Heap section)，new出来的空间都在堆区上。和堆区有一个名字很相近的数据结构——堆(Heap)，虽然名称相近，但两者是完全不同的东西。

因为十大排序算法中有一个堆排序，所以从头开始了解下堆这个数据结构，终学习下堆排序算法。

堆——数据结构

堆是什么

堆的本质是完全二叉树，只不过要在完全二叉树上加一些限制条件。根据加的限制条件的不同，堆又被分为大顶堆和小顶椎。

大顶堆

大顶堆：任意节点的值>=其子节点的值。
如下所示：
在这里插入图片描述

小顶堆

小顶堆：任意节点的值<=其子节点的值。
如下所示：
在这里插入图片描述

堆的实现

接下来我们实现一个大顶堆。

堆的存储与表示

堆的本质是完全二叉树，树形结构可以使用数组和链表进行存储。但是对于完全二叉树来说，使用数组存储更为合适。为什么呢？接下来做个简单分析。
在这里插入图片描述
如果使用数组进行存储，头节点放在数组中下标为0的位置，剩于的所有节点顺序在数组中存放。
这样当我们访问下标为i的结点时：

可以使用2i+i访问它的左子节点
使用2i+2访问它的右子节点
使用 (i-1)/2 访问它的节点
同时，如果计算出的下标大于数组的容量，代表没有此节点

访问堆顶元素

我们知道对于堆来说，堆顶元素存储在数组的0号下标，所以直接返回即可。

元素入堆

要给堆添加元素时，添加的元素可能会破坏堆的成立条件 (对于大顶堆，任意节点的值>=其子节点的值) 。因此添加元素到堆底后，我们要调整堆中节点的位置。

那么一个简单的思路是：比较插入节点与其父节点的值，如果插入节点更大，则将它们交换。然后继续执行此操作，从底至顶修复堆中的各个节点，直至越过根节点或遇到无须交换的节点时结束。

这里最坏的清况是：插入的节点是新的根节点。所以如果整个堆有 $n$ 个节点，二叉树高 $O (l o g n)$ ，此时的时间复杂度为 $O (l o g n)$ 。最好的清况是：插入的节点不需要移动。此时的时间复杂度为 $O (1)$ 。

堆顶元素出堆

堆顶元素出堆后，新的堆顶元素是谁？而且由于堆中少了一个元素，所以堆中剩于元素在数组中的索引会发生变化，所以如何确定新的元素索引呢？

这里的算法为：

交换堆顶元素与堆底元素（交换根节点与最右叶节点）。
交换完成后，将堆底从列表中删除（注意，由于已经交换，因此实际上删除的是原来的堆顶元素）。
从根节点开始，从顶至底执行堆化。

实现代码

#include <iostream>
#include <vector>template <typename T> class Heap {
public:Heap() = default;T peek() { /* Get the top element of the heap */if (data.empty())throw std::runtime_error("Heap is empty");return data[0];}void push(T val) { /* Insert an element into the heap */data.push_back(val);siftUp(data.size() - 1);}void pop() { /* Remove the top element of the heap */if (data.empty()) {throw std::runtime_error("Heap is empty");}std::swap(data[0], data[data.size() - 1]);data.pop_back();siftDown(0);}int size() { return data.size(); }private:std::vector<T> data;inline int left(int i) { return 2 * i + 1; }     // Get the left child of iinline int right(int i) { return 2 * i + 2; }    // Get the right child of iinline int parent(int i) { return (i - 1) / 2; } // Get the parent of ivoid siftUp(int i) {                           // Move the element up the heapwhile (i > 0 && data[parent(i)] < data[i]) { /* Compare with the parent */std::swap(data[parent(i)], data[i]);i = parent(i);}}void siftDown(int i) { // Move the element down the heapwhile (true) {int l = left(i), r = right(i), ma = i;if (l < data.size() && data[l] > data[ma]) {ma = l;}if (r < data.size() && data[r] > data[ma]) {ma = r;}std::swap(data[i], data[ma]);if (ma == i) {break;}i = ma;}}
};int main() {Heap<int> heap;heap.push(1);heap.push(2);heap.push(3);heap.push(4);heap.push(5);std::cout << "Heap size: " << heap.size() << std::endl;std::cout << "Heap top: " << heap.peek() << std::endl;heap.pop();std::cout << "Heap size: " << heap.size() << std::endl;std::cout << "Heap top: " << heap.peek() << std::endl;
}

优先队列

堆通常可以用来实现优先队列，优先队列（Priority Queue）是一种抽象数据类型，类似于普通的队列或堆栈数据结构，但每个元素都有一个优先级。优先级高的元素会优先出队（被处理），而不是按照元素入队的顺序来处理。

堆排序

如果你明白上面的内容后，那么堆排序就比较简单了。
流程如下：

将给定的无序数组建成一个堆(假定是大顶堆)
将堆顶元素弹出
重新对堆中剩于的元素堆化
重复2和3，直到堆中无元素

这里存在一个问题：如何将给定的无序数组建成一个堆？
一个很笨的方法是：我们将无序数组中的元素一个一个取出来，然后push到堆中。伪代码如下：

  std::vector<int> vec{1, 3, 5, 2, 0, 4};Heap<int> heap;for (int i = 0; i < vec.size(); i++) {heap.push(vec[i]);}

如果有 $n$ 个节点的话，这里的时间复杂度为 $O (n l o g n)$ 。

参考链接2，有一个时间复杂度为 $O (n)$ 的建堆方法。

堆排序代码

简单思路版本：

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(std::vector<int> &nums, int n, int i) {while (true) {// 判断节点 i, l, r 中值最大的节点，记为 maint l = 2 * i + 1;int r = 2 * i + 2;int ma = i;if (l < n && nums[l] > nums[ma])ma = l;if (r < n && nums[r] > nums[ma])ma = r;// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出if (ma == i) {break;}// 交换两节点std::swap(nums[i], nums[ma]);// 循环向下堆化i = ma;}
}/* 堆排序 */
std::vector<int> heapSort(std::vector<int> &nums) {// 建堆操作：堆化除叶节点以外的其他所有节点for (int i = nums.size() / 2 - 1; i >= 0; --i) {siftDown(nums, nums.size(), i);}std::vector<int> res; /* 用来收集堆顶元素 */// 从堆中提取最大元素for (int i = nums.size() - 1; i >= 0; --i) {// 交换根节点与最右叶节点（交换首元素与尾元素）std::swap(nums[0], nums[nums.size() - 1]);res.push_back(nums.back());nums.pop_back(); // 将堆顶元素弹出siftDown(nums, nums.size(), 0);  // 重新对堆中剩于的元素堆化}return res;
}int main() {std::vector<int> vec{1, 3, 5, 2, 0, 4};std::vector<int> res = heapSort(vec);for (int i = 0; i < res.size(); i++) {std::cout << res[i] << " ";}
}

上面的这种写法要多定义一个空间复杂度为 $O (n)$ 的结果数组，用来保存结果，这会造成额外的空间浪费。

那么有没有方法可以建堆后，直接对堆进行排序。

答案是有的，每次将堆的顶点和堆底交换后，顶点元素本是要弹出的（目的是对剩于的堆中的元素重新进行排序）。我们可以弹出操作变为动态减少堆的大小。代码如下：

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */
void siftDown(std::vector<int> &nums, int n, int i) {while (true) {// 判断节点 i, l, r 中值最大的节点，记为 maint l = 2 * i + 1;int r = 2 * i + 2;int ma = i;if (l < n && nums[l] > nums[ma])ma = l;if (r < n && nums[r] > nums[ma])ma = r;// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出if (ma == i) {break;}// 交换两节点std::swap(nums[i], nums[ma]);// 循环向下堆化i = ma;}
}/* 堆排序 */
void heapSort(std::vector<int> &nums) {// 建堆操作：堆化除叶节点以外的其他所有节点for (int i = nums.size() / 2 - 1; i >= 0; --i) {siftDown(nums, nums.size(), i);}// 从堆中提取最大元素，循环 n-1 轮, because the last element is the smallestfor (int i = nums.size() - 1; i > 0; --i) {// 交换根节点与最右叶节点（交换首元素与尾元素）std::swap(nums[0], nums[i]);siftDown(nums, i, 0); // every loop, the heap size is reduced by 1}
}int main() {std::vector<int> vec{1, 3, 5, 2, 0, 4};heapSort(vec);for (int i = 0; i < vec.size(); i++) {std::cout << vec[i] << " ";}
}

所以堆排序的时间复杂度应为 $O (n l o g n)$ ，因为for循环n-1次，每一次堆化的复杂度为 $O (l o g n)$ 。

参考链接

https://www.hello-algo.com/chapter_heap/heap/#3
https://www.hello-algo.com/chapter_heap/build_heap/#821