CS161 Lecture 2 数据结构-Min Heap

CS161

---

数据结构的重要性

数据结构会影响算法的复杂度，以Selection Sort为例。Selection Sort伪代码如下：

def selectionSort(L):
    while L is not empty:
        find and remove smallest element x in L
    output x

在伪代码中即使是一行，一句可以表示的东西，实际使用算法逻辑可能是很多句的复杂结构。

选择排序：基础算法

如果用基础的方法，每次扫描整个数组L寻找最小值，那么这个算法的复杂度为：扫描整个L中全部n个元素的时间O(n)，执行此步骤n次。

$$O(\sum_{n=1}^{n} O(n))=O(n^2)$$
总复杂度为$O(n^2)$

选择排序：Priority Queue

定义

Priority Queue是为寻找/移除最小元素优化过的数据结构。它会把元素根据某种函数映射成可比较的优先级，按优先级排列所有元素。

常用运算

在选择排序中，需要用到的运算有：

• 根据列表生成Priority Queue
• 找寻并移除最小值

一般情况下Priority Queue常用的运算还有：

• 插入新元素
• 删除非最小的某个元素
• 更改优先度

实现

Priority Queue最常见的实现方法是使用Binary heap。Binary heap需要O(n)复杂度来生成，每次寻找/删除最小值只需要O(log n)复杂度。就可以把选择排序的整体复杂度下降至$O(n\log n)$。

Binary Heap （此处讨论最小堆）

物理结构和概念结构

最小堆是一个完全二叉树。它在实际的结构上是一个从0开始的列表，但是在概念上是一个树的结构。这就要求每个元素在列表中的索引(Index)要能够满足某些特征以来表示树的结构。
[img]

父节点和子节点

每个节点都可能有子节点(child)或父节点(parent)。没有子节点的是叶节点(leaf)，没有父节点的是根节点(root)。一个节点至多可有2个子节点，1个父节点。
假设物理结构列表名为A，A[i]是一个列表元素，也是一个概念结构的节点，这个A[i]在概念结构的父节点为A[(i-1)//2]。e.g. (5-1)//2=2，(6-1)//2=2，则节点5和节点6同为节点2的子节点。这里所指的都是节点在物理结构列表中的索引。A[i]在概念结构的子节点为A[2*i+1]和/或A[2*i+2]。最小堆的性质(heap property)为父节点的优先级必小于等于子节点的优先级。因为堆的性质只限定了父节点和子节点的关系，所以一个满足堆性质的堆未必在物理结构上就是排好序的，左子节点可能大于右子节点。
[img]
但是因为这个性质，根节点永远为堆中最小值，也就是物理结构列表中的A[0]一定是最小值。

运算：寻找最小值

既然A[0]一定是当前堆的最小值，直接移除根节点并输出就可以了。摘取最后一个元素放在根节点上，这样会打破A[0]-A1,A[2]的堆的性质，但是其他部分不会受影响。所以迭代地把A[0]的大值交换到下面就好了。这个过程，定义一个函数fixheap(i)，i是某个节点的序号，fixheap的作用是修复以x为根节点的子树的堆的性质。

伪代码

def fixheap(x):
    while A[i] has a smaller child:
        j = the index of smallest child of A[i]
        swap A[i] and A[j]
        i = j (then it can continue to the next level)

每一次输出A[0]，然后执行fixheap[0]，直到序列为空。

复杂度分析

每次交换会把i赋值成2i+1或2i+2，此过程进行x次后$i=2^x-1$。但是i必须小于列表长度n所以x不可能大于log n。所以每一次输出A[0]后fixheap[0]的复杂度是$O(\log n)$。
把整个队列n个元素全部输出即为$O(n \log n)$，选择排序复杂度。

运算：以列表生成最小堆：

这个过程可以由递归(recursion)或迭代(iteration)完成。定义一个函数makeHeap(i)。

递归(recursion)方式

伪代码

def makeHeap(i):
    # reorganize subtree under i into a heap structure
    call makeHeap on each child of i
    fixheap(i)

复杂度分析

使用Master Theorem:
定义T(n)为递归地从长度为n的列表生成最小堆的时间。

$$T(n)\leq 2T(\frac{n}{2})+O(\log n)$$
2为每层递归都会调用2个下层递归，$\frac{n}{2}$是每个下层递归参数的个数，$O(\log n)$是每层回归执行的操作的复杂度。根据Master Theorem，T(n)=O(n)。

迭代(iteration)方式

伪代码

for i in n-1, n-2, ..., 0:
    fixheap(i)

复杂度分析

$$T(n)=\sum_{i=0}^{n-1}Time\ for\ fixheap(i)$$
有$\frac{n}{2}$的调用交换了0次（因为是叶节点）；
有$\frac{n}{4}$的调用交换了1次；
有$\frac{n}{8}$的调用交换了2次；......
最终T(n)为O(n)。