1. 定义

二叉堆其实就是一种特殊的二叉树，其每个结点都小于等于其父结点（或者大于等于）。二叉堆能够很好地实现优先队列的操作，同时使用完全二叉树形成的二叉堆可以较为简单的使用数组来进行实现。

2. 算法

以下代码默认二叉堆使用数组进行实现(vec[1]…vec[n] 为堆中结点)，以大顶堆为例(大数在堆顶)

  • 在二叉堆中，如果某个节点的值发生变化，则需要对其做一定的调整以满足二叉堆的定义

    1. //上浮操作为和父结点交换
    2. //每次上浮一层，并和当前父结点比较判断是否需要继续上浮
    3. void swim(vector<int>& vec, int k){
    4.   while(k > 1 && vec[k / 2] < vec[k]){
    5.       swap(vec[k / 2], vec[k]);
    6.       k /= 2;
    7.   }
    8. }
    1. //下沉操作为和子结点中较大者交换
    2. //每次下沉一层，并和当前子结点比较判断是否需要继续下沉
    3. void sink(vector<int>& vec, int k){
    4.   while(2 * k < vec.size()){
    5.       //使用 j 记录较大子结点的下标
    6.       int j = 2 * k;
    7.       if (j + 1 < vec.size() && vec[j + 1] > vec[j]) j = j + 1;
    9.       //判断是否需要继续下沉
    10.       if (vec[k] >= vec[j])
    11.           break;
    12.       swap(vec[k], vec[j]);
    13.       k = j;
    14.   }
    15. }

    由于我们使用的数据结构为完全二叉树，所以每一次上浮或下沉操作可以将搜索空间减半，所以这两个算法的时间复杂度最大为 O(logn)(n为二叉堆中结点的个数)

  1. //将结点置于数组中最后一个位置（等价于二叉堆中最后一层最右边的位置）
  2. //再将其上浮
  3. void insert(vector<int>& vec, int val){
  4.     vec.push_back(val);
  5.     swim(vec, vec.size() - 1);
  6. }
  1. //将第一个结点（堆顶元素）和最后一个结点交换
  2. //删除最后一个结点
  3. //将第一个结点下沉
  4. int top(vector<int>& vec){
  5.     int ret = vec[1];
  6.     vec[1] = vec[vec.size() - 1];
  7.     vec.pop_back();
  8.     sink(vec, 1);
  9.     return ret;
  10. }

这两个算法的复杂度主要来自于调用 swim() 和 sink() 函数，所以时间复杂度最大为 O(logn)(n为二叉堆中结点的个数)。