数据结构和算法分析：第六章优先队列（堆）

- 日理万妓 2022-05-15 14:53 384阅读 0赞

一般来说，短的作业要尽可能地快速结束，这很重要，因此在已经运行的作业当中这些短作业应该拥有优先权。此外，有些作业虽然不短小但很重要，也应该有优先权。

# 6.1 模型 #

优先队列是允许至少以下两种操作的数据结构：insert(插入)，它的作用是插入一个元素；以及deleteMin(删除最小者元素)，它的工作是找出、返回并删除优先队列中最小的元素。insert操作等价于enqueue（入队），而deleteMin操作等价于dequeue（出队）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70]

在**贪婪算法**的实现方面队列也是很重要的，该算法通过反复求一个最小元来进行操作。

# 6.2 一些简单的实现 #

一种实现优先队列的方法是使用二叉树，它对这两种操作的平均运行时间都是O(logN)。

缺陷: 在使用二叉查找树来实现优先队列的时候，我们删除的唯一元素是最小元。反复除去左子树的节点似乎会损害树的平衡、使得右子树加重。然而，右子树是随机的。在最坏的情况下，即deleteMin将左子树删空的情况下，右子树拥有的元素最多就是它应具有的两倍。

# 6.3 二叉堆 #

二叉堆：像二叉查找树一样，堆也有两个性质，即**结构性**和**堆序性**。恰似AVL树，对堆的一次操作可能破快这两个性质中的一个，因此，堆的操作必须到堆的所有性质都被满足时才能终止。

## 6.3.1 结构性质 ##

堆是一颗被完全填充的二叉树。容易证明一个高为h的完全二叉树有2k到2(k+1)-1个节点。这意味着二叉树的高是\[logN\]，显然他是O(logN)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 1]

二叉堆的实现可以用一数组来实现：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 2]

因此一个堆的结构将由一个（Compareable对象的）数组和一个代表当前堆的大小的整形数组组成。

## 6.3.2 堆序性质 ##

在一个堆中，对于每个节点X，X的父亲中的关键字小于或则等于X的关键字，根节点除外（它没有父亲）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 3]

## 6.3.3 基本的堆操作 ##

**insert（插入）**  
insert操作一般的策略叫做**上滤**。为将一个元素插入到堆中，我们在下一个可用的位置创建一个空穴，否则该堆就不是完全树。如果X可以放入空穴中而不破快堆的序，那么插入完成。否则，我们把空穴的父节点上的元素移入该空穴中，这样，空穴就朝着根的方向向上冒一步。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 4]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 5]

**deleteMin（删除最小元）**  
deleteMin操作的一般策略叫做**下滤**。当删除一个最小元的时候，要在根节点建立一个空穴。由于堆中现在少了一个元素了，因此堆中最后一个元素X必须移动到该堆的某个地方。如果X可以被放入到空穴中，那么deleteMin操作完成。不过这一般都不太可能，因此我们将空穴的两个儿子中较少者放入空穴，这样就把空穴向下推了一层。重复该步骤直到X可以被放入空穴中。因此，我们的做法就是将X置入沿着从根开始包含最小儿子的一条路径上的正确位置。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 6]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 7]

## 6.3.4 其他堆的操作 ##

**decreaseKey(降低关键字的值)**  
decreaseKey(p,∆)降低在位置p处的项的值，降低幅度为正的量∆，由于这可能破坏堆序性质，因此必须通过上滤操作来对堆进调整。

**increaseKey(增加关键字的值)**  
iecreaseKey(p,∆)操作增加在位置p处的项的值，增值的幅度为正的量∆。这可以用下滤来完成，许多调度程序自动地降低正在过多地消耗CPu时间内进程的优先级。

**delete(删除)**  
delete§操作删除堆中位置p上的节点。该操作首先执行decreaseKey（p,无穷大），然后再执行deleteMin()操作来完成。

**buildHeap(构建堆)**  
有时候二叉堆是由一些的初始集合构造而得。这种构造方法以N作为输入项，并把他们放到一个堆中。

# 6.9 标准库中的优先队列 #

然而在Java 1.5中出现了泛型类的PriorityQueue,在该类中insert、findMin和deleteMin通过add、element和remove表示。PriorityQueue对象可以通过无参数、一个比较器、或另一个兼容的结合构造出来。

由于优先队列有许多有效的实现方法，因此该类库的设计者没有选择让PriorityQueue成为一个接口。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70]: /images/20220503/681403e69cb8468f87722764012eeb41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 1]: /images/20220503/d5ca4f3a0a8f4dfa93c5b16f52f119dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 2]: /images/20220503/cced410af58b4657b3e3f71e8b8f6e87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 3]: /images/20220503/76483701d2c2404eb6dd1543692526fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 4]: /images/20220503/79664fee766f4d33aafb156085053ca4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 5]: /images/20220503/4e3c3245ebd549c992757f260c219253.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 6]: /images/20220503/8ea47d39ee34443c92a7991461635737.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMTI1MTgz_size_16_color_FFFFFF_t_70 7]: /images/20220503/ac36d85eeeb144bb864ac52853c81a38.png