数据结构——堆，堆排序

前提

我们都知道内存分布中的堆区(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/#821