本篇笔记以小根堆为例。

数据结构

（近似）完全二叉树，存放在树组中，树组角标从1开始，以1为根。

规定：父节点值<子节点值，相邻节点没有大小要求，相邻子树中没有大小要求。

效果：确保树根节点值为全树最小值。

节点i的左子节点为2i，右子节点为2i+1。

节点i的父节点为(int)(i/2)。

我们额外维护一个length变量用于判断数组中的元素是否在树中为有效节点。

push

在树组末尾加入要添加的数x。

此时我们需要将x向上冒泡，冒到它该存在的位置。

（过程同冒泡排序中的冒泡）

get_min

由于小根堆特性，heap[1]即为堆中最小值。

pop_min

将根节点置为0，将末尾元素（叶子节点）放在根中，然后使新根节点下沉，下沉到它该存在的位置。

下沉过程中，每一步都将 当前节点、左子、右子 中的最小值向上冒（与当前节点交换）。

当前步骤中三个节点的最小值已经是当前节点时，堆的维护便完成了。