堆可以维护一个数据集合

1.如何手写一个堆？

1.1 基本操作

1.向集合中插入一个数

2.求集合中的最小值

3.删除最小值

4.删除任意一个元素

5.修改任意一个元素

前 $3$ 个操作STL可以直接实现，后两个不能。

1.2 基本结构

堆是一个二叉树，是完全二叉树

完全二叉树的含义就是：上面的每个点都是满的，最后一层节点我是从左到右排列。

堆的每个点都是小于等于左右儿子的。

堆中某个节点的值总是不大于或不小于其父节点的值。

小根堆的根节点是堆中的最小值

1.3 堆的存储

用一个一维数组存，$1$ 号点是根节点。$x$ 的左儿子是 $2x$，右儿子是 $2x+1$。

1.4 堆的操作

down()把一个节点往上移

up()把一个节点往下移

down()操作：

如果的根节点的值变了，我们就要将堆往下移，设堆变成 $6$，他的下一个值为 $3$，将 $6$ 和 $3$ 交换一下，堆点一定是最小值， 因此我们往下移的时候，要将当前这三个点的最小值交换，否则就不满足一个堆了。只需要满足根节点大于等于儿子节点，左右儿子节点不需要交换。

如果还不满足一个堆的话，继续刚刚的步骤

up() 操作：
如果当前的点小于父节点，那么就和当前的父节点交换……

1.5 堆操作的实现

插入一个数heap[++size]=x up[size]不断往上移

在堆的最后插入

最小值的话一定第一个元素（根节点）是最小的，于是就是heap[1]

删除：将整个堆的最后一个元素覆盖到堆顶，这样堆顶就没了，size--,再down()一遍。

因为删除头部节点非常困难，尾部节点很简单

heap[1]=heap[size--]

让 $1$ 号点往下走 down(1)

删除任意一个元素：heap[k]=heap[size--];

不管三七二十一 down(1) 一遍再 up(1) 一遍

修改任意一个元素： heap[k]=x down(k) up(k)

下标应从 $1$ 开始