数据结构：详解堆和栈

1.堆

堆(Heap))是一种重要的数据结构，是实现优先队列(Priority Queues)首选的数据结构。由于堆有很多种变体，包括二项式堆、斐波那契堆等，但是这里只考虑最常见的就是二叉堆（以下简称堆）。

堆是一棵满足一定性质的二叉树，具体的讲堆具有如下性质：父节点的键值总是不大于它的孩子节点的键值（小顶堆）, 堆可以分为小顶堆和大顶堆，这里以小顶堆为例，其主要包含的操作有：

• insert()

• extractMin

• peek(findMin)

• delete(i)

由于堆是一棵形态规则的二叉树，因此堆的父节点和孩子节点存在如下关系：

设父节点的编号为 i, 则其左孩子节点的编号为2*i+1, 右孩子节点的编号为2*i+2

设孩子节点的编号为i, 则其父节点的编号为(i-1)/2

由于二叉树良好的形态已经包含了父节点和孩子节点的关系信息，因此就可以不使用链表而简单的使用数组来存储堆。

要实现堆的基本操作，涉及到的两个关键的函数

siftUp(i, x)： 将位置i的元素x向上调整，以满足堆得性质，常常是用于insert后，用于调整堆；

siftDown(i, x)：同理，常常是用于delete(i)后，用于调整堆；

可以看到siftUp和siftDown不停的在父节点和子节点之间比较、交换；在不超过logn
的时间复杂度就可以完成一次操作。有了这两个基本的函数，就可以实现上述提及的堆的基本操作。

首先是如何建堆，实现建堆操作有两个思路:

• 一个是不断地insert（insert后调用的是siftUp）

• 另一个将原始数组当成一个需要调整的堆，然后自底向上地在每个位置i调用siftDown(i)，完成后我们就可以得到一个满足堆性质的堆。这里考虑后一种思路：

通常堆的insert操作是将元素插入到堆尾，由于新元素的插入可能违反堆的性质，因此需要调用siftUp操作自底向上调整堆；堆移除堆顶元素操作是将堆顶元素删除，然后将堆最后一个元素放置在堆顶，接着执行siftDown
操作，同理替换堆顶元素也是相同的操作。

建堆

那么建堆操作的时间复杂度是多少呢？答案是O(n)。虽然siftDown的操作时间是logn，但是由于高度在递减的同时，每一层的节点数量也在成倍减少，最后通过数列错位相减可以得到时间复杂度是O(n)。

extractMin

由于堆的固有性质，堆的根便是最小的元素，因此peek操作就是返回根nums[0]元素即可；

若要将nums[0]删除，可以将末尾的元素nums[n-1]覆盖nums[0],然后将堆得size = size-1，调用siftDown(0)调整堆。时间复杂度为logn。

peek

同上

delete(i)

删除堆中位置为i的节点，涉及到两个函数siftUp和siftDown，时间复杂度为logn,具体步骤是，

• 将元素last覆盖元素i，然后siftDown

• 检查是否需要siftUp

注意到堆的删除操作，如果是删除堆的根节点，则不用考虑执行siftUp的操作；若删除的是堆的非根节点，则要视情况决定是siftDown还是siftUp操作，两个操作是互斥的。