数据结构之堆和优先队列

清疚 2023-01-03 01:56 30阅读 0赞

**目录**

堆和优先队列的应用

堆排序

任务调度

包裹分拣

霍夫曼编码

负载均衡

堆的描述

优先队列的描述

问与答

左平衡二叉树特别适合存储于数组中，为什么这种性质并不是对所有的二叉树都成立？

假设我们用一个优先队列存放一些已经由应用程序预先设定好顺序的任务，如果系统不断地处理大量高优先级的任务时，系统可能会产生什么样的问题？如何解决这些问题？

--------------------

在许多问题中，当对数据集进行频繁的插入和删除操作时，往往需要快速确定最大或最小的元素。处理这种问题的方法之一，就是使用一个已经排好序的数据集。通过这种方法，最大或最小的元素总是处在数据集的头部（这取决于升序还是降序）。然而将数据集一遍又一遍地排序代价非常高，很多情况下，将元素排序并不是操作的目的，最终我们可能在真正要做的工作外做了许多其他的工作。想要快速找到最大或最小元素，只需要让元素存储在可以找到它的位置上就行。堆和优先队列就是一种处理这种问题的有效方法。

**堆**：是一种树形组织，使我们能够迅速确定包含最大值的节点。维持一棵树的代价低于维持一个有序数据集的代价。同样，我们可以通过堆快速找到包含最小值的元素。

**优先队列**：它是一个从**堆**自然衍生而来的数据结构。在优先队列中，数据保存在一个堆中，这样我们能够迅速确定下一个最高优先级的节点。所谓元素的“优先级”在不同的问题中意义也不同。

# 堆和优先队列的应用 #

## 堆排序 ##

在堆排序中，要排序的数据首先存储在一个堆中。从堆中一次取出一个节点，放置到有序数据集的尾部。当取出每个节点时，它的下一个节点就会浮现到堆的顶部。堆排序和快速排序有相同的时间复杂度，但在实际中，快速排序往往比堆排序复杂度略低，两者相差一个常量因子。

## 任务调度 ##

任务调度会告诉操作系统接下来那个进程将在CPU上运行。操作系统会不断调整进程的优先级。用**优先队列**来存储进程是相对比较高效的方法，因为它可以确保下一个将在CPU中运行的进程的优先级是最高的。

## 包裹分拣 ##

快递公司通常用包裹分拣法来确定包裹递送的优先级。当扫描包裹时，高优先级的包裹将作为急件投递出去。计算机系统通常使用**优先队列**来保证最高优先级的包在系统中运行最流畅。

## 霍夫曼编码 ##

这是一种数据压缩编码，它使用霍夫曼树为数据符号分配编码。向出现频率较高的符号分配较短的编码，向出现频率较低的符号分配较长的编码。霍夫曼树石油娇小的二叉树两两合并构成的。由于每次都必须合并键值较小的二叉树。因此每次合并的两棵树都是从一个优先队列中取出的。

## 负载均衡 ##

它用来维护管理一系列处理类似任务的服务。当连接请求到达时，优先队列可以确定哪个服务器能够最好地处理到达的任务

# 堆的描述 #

堆是一颗二叉树，这样的二叉树是局部有序的，任何节点与其兄弟节点之间都没有必然的顺序联系，但是它与父子节点之间有大小顺序关系，按照关系的不同，分为**最大值堆**和**最小值堆**：

*  **最大值堆**：子节点比父节点小的堆，根节点是树中最大的节点。
 *  **最小值堆**：子节点比父节点大的堆，根节点是树中最小的节点。

堆是左平衡的树，所以随着节点的增加，树会逐级从左至右增长。因此对于一个堆来说，一个比较好的表示左平衡二叉树的方式是：将节点通过水平遍历的方式连续存储到一个数组中。假设有一个零索引数组，这表示数组中处于位置i处的节点，其父节点位于（i-1）/2处，计算时忽略小数部分。其左节点和右节点分别位于2i+1和2i+2处。这样的组织结构对于堆来说非常重要，因为通过它我们能够迅速定位堆的最后一个节点：最后一个节点位于树中最深层的最右端。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70][]

比如值为19的节点的左右节点为9和18，它们在数组中的下标为2\*4+1=9,2\*4+2=10。

# 优先队列的描述 #

优先队列将数据按照优先级顺序排列，一个优先队列由许多有序的元素构成，所以优先级最高的元素可以有效而快速地确定。我们可以通过很多方法来实现一个优先队列，最简单常用的方法是维护一个有序数据集，优先级最高的元素位于数据集的头部。然而插入或提取元素之后必须重新排列数据集，该操作的复杂度为O(n)，更好的办法是用一个局部有序的堆来实现优先队列。这样插入或提取一个元素操作的复杂度为O(lg n)。

# 问与答 #

## 左平衡二叉树特别适合存储于数组中，为什么这种性质并不是对所有的二叉树都成立？ ##

之所以左平衡二叉树很适合存储到数组中，是因为在位置0和n-1之间肯定会用到节点（n为节点的个数），如果不是左平衡二叉树，那么数组中就会有没用到的节点，会有空缺。

## 假设我们用一个优先队列存放一些已经由应用程序预先设定好顺序的任务，如果系统不断地处理大量高优先级的任务时，系统可能会产生什么样的问题？如何解决这些问题？ ##

当优先级高的元素不断被插入一个优先队列时，那些低优先级的元素可能永远没机会排列到队列的顶部。例如，在一个任务调度程序中，这种情况会导致低优先级的任务“饿死”。为了解决这个问题，通常系统要采取某种机制来提高任务的等级（随着任务在队列中等待的时间变得越来越长）。这样的话，即使在一个充斥着高任务的繁忙系统中，低优先级的任务最终将获得足够高的优先级，从而排列到队列的顶部。操作系统会频繁地使用这种方法来确保低优先级的进程不会完全“停止”。

当高优先级的元素不断地被插入一个优先队列中

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70]: /images/20221119/aab12c0ba6ca4af6b460a318dd2f0061.png