堆（优先级队列）

一、定义

此处堆指二叉堆，是一棵二叉树，并且是完全二叉树（只有最后一层的右边部分可能存在空缺），每个节点都会有一个权值。对于大根堆来说，父亲的权值不小于儿子的权值（同理可以得到小根堆），树根root是最大值。

二、原理

使用数组模拟二叉树，同时使用 $0$ 号下标的元素。主要使用向上调整和向下调整来保证堆的性质。灵活运用两种调整方式可以实现很多操作。

使用 $0$ 号下标，则节点 $i$ 的孩子节点为 $2\times i + 1,2\times i + 2$ ；不使用 $0$ 号下标，则节点 $i$ 的孩子节点为 $2\times i, 2\times i + 1$ 。
使用 $0$ 号下标，找寻父亲节点下标 $\lfloor\frac{i - 1}{2}\rfloor$ ；不使用 $0$ 号下标，找寻父亲节点下标 $\lfloor\frac{i}{2}\rfloor$ 。

向上调整：

如果一个节点的权值大于他父亲节点的权值，那么交换他们俩，重复该过程，不断向上，直到条件不满足或者遇到根节点。

向下调整：

如果一个节点的权值小于他的孩子的权值，那么则把他最大的孩子与他交换，不断向下，直到条件不满足或者超出容器范围。

void up(int x) {
  while (x > 1 && h[x] > h[x / 2]) {
    swap(h[x], h[x / 2]);
    x /= 2;
  }
}

void down(int x) {
  while (x * 2 <= n) {
    t = x * 2;
    if (t + 1 <= n && h[t + 1] > h[t]) t++;
    if (h[t] <= h[x]) break;
    std::swap(h[x], h[t]);
    x = t;
  }
}

三、实现

1.建堆

可以从根节点开始，对每个节点上滤，可以保证该节点是路径上的最小值，前面的是建好的堆，因此需要从前往后上滤。

也可以从叶子节点开始，对每个节点下滤，可以保证该节点是路径上的最大值，后面是建好的堆，因此需要从后往前下滤。

1 2	void build() {for(int i = 1; i <= n; ++i) up(i);} void build() {for(int i = n; i >= 1; --i) down(i);}

2.push

将一个节点加入容器末尾，然后上滤（因为前面都已经是堆的结构）。

3.pop

将末尾节点与 $0$ 号节点交换，然后删除末尾节点，然后对 $0$ 号节点下滤。

4.top

返回 $0$ 号节点。

6.其他操作

可以修改某个节点的值，单点修改。如果是大根堆，增加该点的值，需要上滤；减小该点的值，需要下滤。

使用模板函数实现priority_queue。其中模板中不仅仅可以放 class T，还可以自己定义其他的模板类型比如 class Container = vector<T>。使用内置的仿函数 less, greater实现比较大小，仿函数必须要创建对象，因为运算符 $()$ 不是静态的，只有创建对象之后才能访问该运算符。

// 默认大顶堆
template <class T, class Container = vector<T>, class Cmp = less<T>>
class Heap
{
private:
    Container elements;
    Cmp cmp; // 仿函数使用时必须要先创建对象
private:
    int getFa(int i) { return (i - 1) >> 1; }
    int getLc(int i) { return (i << 1) + 1; }
    int getRc(int i) { return (i + 1) << 1; }
    void adjustUp(int cur)
    {
        int fa;
        while (cur > 0)
        {
            fa = getFa(cur);
            if (cmp(elements[cur], elements[fa]))
                break;
            swap(elements[fa], elements[cur]);
            cur = fa;
        }
    }
    void adjustDown(int cur)
    {
        int bigIndex;
        while ((bigIndex = getLc(cur)) < size())
        {
            if (bigIndex + 1 < size() && cmp(elements[bigIndex], elements[bigIndex + 1]))
                ++bigIndex;
            // 大顶堆
            if (cmp(elements[bigIndex], elements[cur]))
                break;
            swap(elements[cur], elements[bigIndex]);
            cur = bigIndex;
        }
    }

public:
    Heap() {}
    template <class InputIterator>
    Heap(InputIterator first, InputIterator last)
    {
        while (first != last)
        {
            elements.push_back(*first);
            ++first;
        }
        for (int i = size() - 1; i >= 0; --i)
            adjustDown(i);
    }

    void push(const T &x)
    {
        elements.push_back(x);
        adjustUp(size() - 1);
    }
    void pop()
    {
        swap(elements[0], elements[size() - 1]);
        elements.pop_back();
        adjustDown(0);
    }

    const T &top() const
    {
        return elements[0];
    }

    bool empty() { return elements.empty(); }

    // 函数名后加 const，不能修改成员变量
    int size() const { return elements.size(); }
};

四、应用

1.对顶堆

对顶堆可以用来动态维护一个序列上第 $k$ 大的数， $k$ 值可能会发生改变。

对顶堆由一个大根堆与一个小根堆组成，小根堆维护大值即前 $k$ 大的值（包含第 $k$ 个），大根堆维护小值即比第 $k$ 大数小的其他数。

这两个堆构成的数据结构支持以下操作：

维护：当小根堆的大小小于 $k$ 时，不断将大根堆堆顶元素取出并插入小根堆，直到小根堆的大小等于 $k$ ；当小根堆的大小大于 $k$ 时，不断将小根堆堆顶元素取出并插入大根堆，直到小根堆的大小等于 $k$ ；
插入元素：若插入的元素大于等于小根堆堆顶元素（说明插入的元素有可能成为第 $k$ 大），则将其插入小根堆，否则将其插入大根堆，然后维护对顶堆；
查询第 $k$ 大元素：小根堆堆顶元素即为所求；
删除第 $k$ 大元素：删除小根堆堆顶元素，然后维护对顶堆；
$k$ 值 $+1/-1$ ：根据新的 $k$ 值直接维护对顶堆。

显然，查询第 $k$ 大元素的时间复杂度是 $O(1)$ 的。由于插入、删除或调整 $k$ 值后，小根堆的大小与期望的 $k$ 值最多相差 $1$ ，故每次维护最多只需对大根堆与小根堆中的元素进行一次调整，因此，这些操作的时间复杂度都是 $O(\log n)$ 的。

比如动态求中位数：

295. 数据流的中位数 | Luobuyu’s Blog