堆和堆的应用:堆排序和优先队列

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)后,用于调整堆;

具体的操作如下:

可以看到siftUpsiftDown不停的在父节点和子节点之间比较、交换;在不超过logn的时间复杂度就可以完成一次操作。

有了这两个基本的函数,就可以实现上述提及的堆的基本操作。

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

  • 一个是不断地insertinsert后调用的是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的节点,涉及到两个函数siftUpsiftDown,时间复杂度为logn,具体步骤是,

  • 将元素last覆盖元素i,然后siftDown
  • 检查是否需要siftUp

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

case 1 :

删除中间节点i21,将最后一个节点复制过来;

这里写图片描述

由于没有进行siftDown操作,节点i的值仍然为6,因此为确保堆的性质,执行siftUp操作;

这里写图片描述

case 2

删除中间节点i,将值为11的节点复制过来,执行siftDown操作;
这里写图片描述

由于执行siftDown操作后,节点i的值不再是11,因此就不用再执行siftUp操作了,因为堆的性质在siftDown操作生效后已经得到了保持。

这里写图片描述


可以看出,堆的基本操作都依赖于两个核心的函数siftUpsiftDown;较为完整的Heap代码如下: