MIT 6006 Lecture 4——堆与堆排序

Posted on | In , ,

堆：一种特殊的完全二叉树，其中父节点恒小于等于（大于等于）子节点的值，此堆称为小顶堆（大顶堆）。

优先队列（Priority Queue）

堆的一个很重要的应用就是作为优先队列的数据结构，所以本节我们以优先队列为引子，看一看堆的一些特性和使用方法。

优先队列的定义及基本操作

定义

给定一个集合$S$，集合中的每一个元素都与一个索引键值key对应，其中每个元素都有一个优先级，在优先队列中，我们希望能够快速找到最高优先级的对象。

操作

这里我们定义一些基本操作：

  • $\textrm{insert}(S,x)$：将$x$插入$S$中
  • $\max(S)$：返回$S$中key最大的元素
  • $\textrm{extract_max}(S)$：返回key最大的元素并将其移除
  • $\textrm{increase_key}(S,x,k)$：将$x$的key的优先级更新为$k$

堆（Heap）

堆是一个完全二叉树，我们可以用数组对其进行表示，一个示意图如下，注意数组下标是从1开始的，这样比较好记：

将树堆化

  • root：第一个元素(i=1)
  • 父节点：i/2的节点
  • 左子节点：2i
  • 右子节点：2i+1

大（小）顶堆

特性

父节点的值比子节点大（小），所以寻找最大元素是很方便的，只要返回堆顶元素即可。

堆的操作

建大顶堆

大顶堆化

将一个无序的数组转换成为一个大顶堆，为了实现这个过程，我们需要将数组“大顶堆化”：将一个不是大顶堆的树，通过某种变换，转换为一个大顶堆树，我们通过自下而上的递归方式进行（因为叶子节点一定是大顶堆），令大顶堆化的操作为$\textrm{max_heapify}(A,i)$，即对数组$A$在节点$i$处执行大顶堆化操作，同时，我们假设$i$的左子节点和右子节点已经完成了大顶堆化的操作，其左右子树为大顶堆。现在，我们以一个实例来看一看大顶堆化的具体过程。

下图展示了一个堆，注意到在值为4的节点处出现了冲突，所以这个堆不是一个大顶堆，我们要在值为4的节点处执行$\textrm{max_heapify}$操作，根据我们上面的约定，4的节点编号为2，故我们需要执行$\textrm{max_heapify}(A,2)$。

$\textrm{MAX_HEAPIFY}(A,2)$

​ $\textrm{heap_size}(A)=10$

​ $\textrm{exchange with bigger child: swap(A[2], A[4])}$

​ $\textrm{call MAX_HEAPIFY}(A,4)$

下面分析一下时间复杂度，首先树是一个几乎完全二叉树，以及根据限制，左子树和右子树已经是大顶堆，所以这个时间复杂度被限制在$\log(n)$。

根据max_heapify创建堆

下面我们利用上面的算法，将$A[1…n]$转换为一个大顶堆，我们的算法名称为build_max_heap，其逻辑如下：

$\textrm{build_max_heap}(A)$:

​ $\textrm{for }\ i=n/2\ \ \textrm{ downto }\ 1$

​ $\textrm{max_heapify}(A,i)$:

为什么从$n/2$开始呢？因为$A[n/2+1,…,n]$全部都是叶子节点，而叶子节点已经是大顶堆了，所以自然满足假设，而从$n/2$到$1$，实际上是一个自底向上的过程。

从直观上来看，这个操作的时间复杂度为$O(n\log(n))$，但是实际上这个时间复杂度要更低一些。当节点$i$比叶子节点高一层时，max_heapify需要1次操作，时间复杂度为$\Theta(1)$；而当节点$i$比叶子节点高$l$层时，max_heapify需要$l$次操作，时间复杂度为$\Theta(l)$。我们令叶子层为第0层，那么第一层有$n/4$个节点，需要1次操作，第2层有$n/8$个节点，需要两次操作，第$\log(n)$层有1个节点，需要$\log(n)$次操作，所以时间复杂度为：

令$n/4=2^k$，并提取公因式，那么上式可以写为

后面的级数是一个收敛级数，所以实际上我们的时间复杂度为$\Theta(n)$

堆排序

利用堆的特性，我们可以进行排序操作。

作业

数字电路仿真

问题背景

组合逻辑电路是由门构成的，门以逻辑电平（真/1，假/0）作为输入信号，输出信号是输入信号的函数，逻辑门的计算是需要时间的，假设延迟时间为$\delta$，那么在$\tau$时刻的输出信号对应$\tau-\delta$时刻的输入信号。门的输出信号也是逻辑电平，可以通过电路与其他门相连，将输出信号作为下一个门的输入信号，例如，一个两输入、延迟时间为2ns的异或门的真值表如下：

Time(ns) Input A Input B Output O Explanation
0 0 0 Inputs at time -2
1 0 1 Inputs at time -1
2 1 0 0 0 XOR 0，在第0时刻输出
3 1 1 1 0 XOR 1，在第1时刻输出
4 1 1 XOR 0，在第2时刻输出
5 0 1 XOR 1，在第3时刻输出

电路模拟器通过一个输入文件描述电路的布局，包括门延迟时间、待监测的门以及输入信号。随后以时间序列的方式对整个电路的信号变换过程进行仿真并输出结果，同时也会输出待监测的门的信号变换情况。现在，给定一个仿真代码，然后你需要对代码进行测试，找到性能瓶颈及产生原因，并对性能瓶颈进行优化，点击此处下载代码。解压缩后进入circuit/文件夹，电路仿真文件为circuit.py，输入文件为tests/5devadas13.in，但是对这个文件的仿真时间过长。我们提供了测试文件，测试文件为test-circuit.py。

题目一

在python的代码性能分析器下运行仿真程序，找到最耗时的函数，请在cmd命令行下运行下面这行代码，并根据结果分析哪个函数运行时间最长，如果有多个函数执行时间相同，忽略简单的那个。注意，请不要使用powershell运行：

1
python -m cProfile -s time circuit.py < tests/5devadas13.in

执行完上面这行命令大概需要一两分钟。运行完成后，我们得到的结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
625762426  102.299    0.000  102.299    0.000 circuit.py:286(__lt__)
   259964  102.299    0.000  204.606    0.001 circuit.py:381(_find_min)
    32768    4.087    0.000    4.087    0.000 {method 'write' of '_io.TextIOWrapper' objects}
    64400    0.591    0.000  206.397    0.003 circuit.py:423(step)
828801/634389    0.229    0.000    0.286    0.000 {built-in method builtins.len}
   194381    0.177    0.000  204.791    0.001 circuit.py:361(min)
    65554    0.144    0.000    0.309    0.000 circuit.py:163(transition_output)
    65583    0.119    0.000    0.176    0.000 circuit.py:268(__init__)
        1    0.112    0.112  206.614  206.614 circuit.py:456(run)
    65583    0.089    0.000    0.163    0.000 circuit.py:368(pop)
    65554    0.063    0.000    0.079    0.000 circuit.py:33(output)

可以看出，忽略掉__lt__函数，那么性能的瓶颈为_find_min函数，一共被调用了255964次。

题目二

阅读_find_min的源代码，并指出_find_min实际是在执行哪种数据结构，假设一共有$n$个元素，时间复杂度是多少？

1
2
3
4
5
6
7
8
9
10
11
12
13
def _find_min(self):
    # Computes the index of the minimum element in the queue.
    #
    # This method may crash if called when the queue is empty.
    if self.min_index is not None:
        return
    min = self.queue[0]
    self.min_index = 0
    for i in xrange(1, len(self.queue)):
        key = self.queue[i]
        if key < min:
            min = key
            self.min_index = i

从上面的代码中我们可以看出，_find_min实际上是在一个数组中顺序查找最小的元素，即基于数组的优先队列。在最坏的情况下，需要遍历所有的$n$个元素，所以时间复杂度为$\Theta(n)$。

题目三

如果使用最高效的数据结构，那么请问在$n$个元素的情况下其渐近紧范围（asymptotically tight bound）是多少？

Heap 实现

这里参考STL库实现一个heap操作，由于STL库模板有一些额外的函数支持，所以这里的容器简单地选为vector<int>，算法分别实现push_heap、pop_heap、sort_heap和make_heap四个操作。

push_heap

对于push_heap操作，我们先将元素插入底层的vector的end()位置，然后将该节点与父节点进行比较交换操作并重复这个上溯过程，最后将节点放置到正确的位置上。我们的函数接受两个迭代器，用来表示heap底部容器的头尾，需要注意的是头尾迭代器表示的范围是左闭右开的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef vector<int>::iterator VectorIterator;

void __push_heap(VectorIterator first, int holeIndex, int topIndex, int value);

// 应当注意的是，当调用push_heap时，新元素应当已经位于底层容器的末尾
inline void push_heap(VectorIterator first, VectorIterator last){
    __push_heap(first, (last-first)-1, 0, *(last-1));
}

void __push_heap(VectorIterator first, int holeIndex, int topIndex, int value){
    // first: 绝对坐标下容器的起始值
    // holeIndex: 相对坐标下容器的末位位置
    // topIndex: 相对坐标系下容器的起始位置
    // value: holeIndex的值
    int parent = (holeIndex - 1)/2;   
    while(holeIndex > topIndex && *(first+parent) < value){  // 当尚未到堆顶且parent的值小于插入值
        *(first + holeIndex) = *(first + parent);            // 下放parent
        holeIndex = parent;                                  // 调整holeIndex和parent的index
        parent = (holeIndex-1)/2;
    }
    *(first + holeIndex) = value;                            // 最后在正确的位置插入值
}

参考文献

0%