数据结构——堆，堆排序

前提

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

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

堆——数据结构

堆是什么

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

大顶堆

大顶堆：任意节点的值>=其子节点的值。
如下所示：

小顶堆

小顶堆：任意节点的值<=其子节点的值。
如下所示：

堆的实现

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

堆的存储与表示

堆的本质是完全二叉树，树形结构可以使用数组和链表进行存储。但是对于完全二叉树来说，使用数组存储更为合适。为什么呢？接下来做个简单分析。

如果使用数组进行存储，头节点放在数组中下标为0的位置，剩于的所有节点顺序在数组中存放。
这样当我们访问下标为i的结点时：

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

访问堆顶元素

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

元素入堆

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

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

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

堆顶元素出堆

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

这里的算法为：

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

实现代码

#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 i   inline int right(int i) { return 2 * i + 2; }    // Get the right child of i   inline int parent(int i) { return (i - 1) / 2; } // Get the parent of i    void siftUp(int i) {                           // Move the element up the heap     while (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 heap     while (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）是一种抽象数据类型，类似于普通的队列或堆栈数据结构，但每个元素都有一个优先级。优先级高的元素会优先出队（被处理），而不是按照元素入队的顺序来处理。

堆排序

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

1. 将给定的无序数组建成一个堆(假定是大顶堆)
2. 将堆顶元素弹出
3. 重新对堆中剩于的元素堆化
4. 重复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(nlogn)$。

---

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

堆排序代码

简单思路版本：

/* 堆的长度为 n ，从节点 i 开始，从顶至底堆化 */ void siftDown(std::vector<int> &nums, int n, int i) {   while (true) {     // 判断节点 i, l, r 中值最大的节点，记为 ma     int 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 中值最大的节点，记为 ma     int 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 smallest   for (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(nlogn)$，因为for循环n-1次，每一次堆化的复杂度为$O(logn)$。

参考链接

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