堆，是一种十分有用的数据结构，其优异的时间复杂度决定了它在求区间最大值（或最小值）中的地位。尽管堆也有极大的局限性，但它仍然是我们在算法竞赛中的一种常用数据结构。

概念

  堆，本质上是一个完全二叉树。同时，堆满足父亲节点一定不大于（或不小于）儿子节点的性质。常见的堆有二叉堆与斐波那契堆等。从时间复杂度上来讲，斐波那契堆是比二叉堆要优一些的（但本蒟蒻没学23333）。为了方便，我们实际上使用的一般是$STL$提供的优先队列（二叉堆）。

二叉堆的实现

1.手写实现（不建议）

  要手写实现二叉堆，首先你需要知道其原理。

  二叉堆是堆的一种基本实现方式，其结构为一个完全二叉树（或近似完全二叉树）如图：

  二叉堆的优异的时间复杂度（$O(logn)$）就源于该结构。

  利用完全二叉树的性质，我们可以很便利地处理任意一个节点的子节点（除了叶子节点）。

  依据完全二叉树的性质，我们可以采用层次序列储存方式，直接用数组来储存二叉堆。层次序列储存方式就是逐层从左到右堆对节点进行编号，将次编号作为其对应的数组下标。在这种储存方式中，父节点编号一定为子节点编号除以2，左子节点编号为父节点编号乘以2，右子节点编号为父节点编号的二倍加1；即上图所示编号。

  储存好之后就形成了下图（以大根堆为例）：

  下面，我们就以大根堆为例来解释一下二叉堆的实现过程。

1.插入（本文用$add$来表示）

  $insert$操作就是在二叉堆中插入一个新的带权值$val$的节点。显然，只要我们当前的二叉堆满足大根堆性质。那么，我们将新的节点加到二叉树的最后一个节点后，如图：

  如果我们已$val=20$为例。显然，当我们将该点加入后，二叉树并不满足大根堆性质，但由于大根堆中仅要求父节点严格大于等于子节点，所以我们可以将新插入的12号节向上与父节点交换，直到当前父节点比当前节点大为止。
如下图：

  很容易发现，按照上述方法进行操作，一定能维护其大根堆性质。

代码参见大根堆模板 $up$ 函数及 $add$ 函数。

2.删除（本文用$del$表示）

  删除，可以分为两种类型：删除堆顶，和删除某一位的元素（没啥用）。

  我们以删除堆顶为例。我们可以发现，如果我们将堆顶删除，那么一般情况下，我们的二叉树将不满足大根堆性质（如图1）。所以我们将原堆顶的两个儿子相比较，将较大的设为新的堆顶。但是这样的话，可能会导致该子节点所在子树不满足大根堆性质，所以我们要将这个子树看做是一个需要删除堆顶的大根堆对其进行操作（堆顶已移到其父节点）。不断重复上述操作（如图2、3），直至没有子树（叶节点）为止（如图4），并将该节点设为空。
如下图：

  可以发现，如果我们在删点前将堆顶设为0，那么实际上删点时维护大根堆性质的操作与插入时正好相反。所以我们可以先将堆顶$top$的值更改为0，再对整个二叉树进行插入时$up$操作的逆运算。即可维护堆性质。

代码参见大根堆模板中的 $down$ 与 $del$ 函数。

3.取堆顶值（本文以$top$表示）

  我们是在二叉树的基础上构建堆的结构的。所以堆顶我们可以已知保持为二叉树的树根，在完全二叉树中即为根节点。故我们可以将根节点上的值直接返回，即为堆顶值。

代码参见大根堆模板的 $top$ 函数。

2.STL1

  从某种程度上说，STL真是造福万家。

  在$STL$中，有一个叫做优先队列的数据结构，即priority_queue（位于#include<queue>库中），它本质上就是一个二叉堆。

  priotity_queue支持以下操作：

  push(n)将 $n$ 插入二叉堆。

  pop()将二叉堆堆顶顶删除

  top()返回二叉堆顶值

  size()返回二叉堆的大小

  empty()若二叉堆为空，返回true，否则返回false。

3.STL2

  除被命名为“优先队列”的位于#include<queue>中的二叉堆priority_queue外，$STL$还提供了另外的一种堆heap（位于#include<algorithm>库中）。

  这种堆与“优先队列”不同，heap只能依附于数组存在，由于博主并没有对该结构进行深度学习，这里不多叙述。