承德400电话申请开通【承德企业网站建设】承德微信公众号小程序开发运营价格、承德微信公众号APP软件客户端设计运营、承德网页页面设计公司费用、承德公司网站制作方案流程改版维护大概需要多少钱

承德400电话申请开通【承德企业网站建设】承德微信公众号小程序开发运营价格、承德微信公众号APP软件客户端设计运营、承德网页页面设计公司费用、承德公司网站制作方案流程改版维护大概需要多少钱

承德，河北省地级市，河北省政府批复确定的河北国际旅游城市、连接京津辽蒙的区域性中心城市 [1]  。截至2019年，全市下辖3个区、4个县、代管1个县级市和3个自治县，总面积39519平方公里，常住人口347.32万人，城镇人口180.85万人，城镇化率52.07%。 [2] 

承德地处中国东北地区、河北省东北部，南邻京津，北接赤峰和锡林郭勒，东西与朝阳、秦皇岛、唐山、张家口相邻，距省会石家庄435公里，距北京225公里。 [3]  是连接京津冀辽蒙的重要节点，具有“一市连五省”的独特区位优势，是国家甲类开放城市，中国普通话标准音采集地、中国摄影之乡、中国剪纸之乡。 [4] 

承德是首批国家历史文化名城，1703年清康熙修建避暑山庄，成为清王朝的第二个政治中心；1723年设热河厅；1733年雍正取“承受先祖德泽”之义；赐字“皇承天德”释义先皇秉承天地化育万物的恩德； [5]  设承德直隶州，始称“承德”；民国和解放初期为原热河省省会；1955年，热河省建制撤销，承德划归河北省，为省辖市。承德的避暑山庄及其周围寺庙是中国十大风景名胜、旅游胜地四十佳、国家重点风景名胜区，被联合国教科文组织批准为世界文化遗产，也是国家首批世界文化遗产。 [4] 

2012年，承德被评为中国“十大特色休闲城市”。2016年11月，承德市被中华人民共和国国家旅游局评为第二批国家全域旅游示范区。2017年10月，承德市入选国家森林城市。 [6]  2017年12月，获得“厕所革命优秀城市奖”。

5.9　优先级队列和偏序树

到目前为止，我们只看到一种抽象数据类型——词典，以及它的一种实现——二叉查找树。本节将研究另一种抽象数据类型以及它最有效率的一种实现。这种叫作优先级队列的抽象数据类型是各自有优先级与之关联的一组元素。例如，这些元素可以是一些记录，而优先级则可能是记录中某个字段的值。与优先级队列ADT有关的两种操作如下：

1. 向集合中插入一个元素（insert）；

2. 从集合中找出优先级最高的元素并将其删除（这种组合操作称为deletemax），被删除的元素由该函数返回。

示例 5.26

分时操作系统从多个来源接受服务请求，而这些作业的优先级可能不尽相同。例如，优先级最高的可能是系统进程，这些进程中可能包含监控传入数据（比如在终端的按键动作生成的信号，或是局域网上数据包的到达所生成的信号）的“守护进程”。接着可能是用户进程，那些由普通用户发出的指令。再下来就可能是某些特定的后台作业，比如向磁带备份数据，或是用户已指定以低优先级运行的长计算。

作业可以表示为记录，这种记录由对应作业的整数ID和对应作业优先级的整数组成。也就是说，可以使用如下结构体

struct ETYPE {
    int jobID;
    int priority;};复制代码

表示优先级队列中的元素。在初始化新的作业时，它会得到一个ID和一个优先级。然后对等待服务的作业构成的优先级队列执行这一元素的插入操作。当处理器资源可用时，系统就会来到优先级队列，并执行deletemax操作。由该操作返回的元素就是等待服务的作业中优先级最高的作业，而该作业正是接下来要执行的。

示例 5.27

我们可以使用优先级队列ADT实现排序算法。假设有一列整数a1、a2、…、an 要排序，可以将这些整数放入一个优先级队列，分别使用这些元素的值作为各自的优先级。如果随后执行deletemax操作n 次，这些整数就会按照从大到小的顺序依次被选出来。5.10节还会更详细地讨论这种称为堆排序的算法。

5.9.1　偏序树

实现优先级队列的一种有效方式是使用偏序树（Partially Ordered Tree，POT），这是一种具有如下属性的带标号二叉树。

1. 节点的标号是具有“优先级”的元素，该优先级可以是元素的值，也可以是元素某个组成部分的值。

2. 存储在节点中的元素的优先级，不小于存储在其子节点中的元素的优先级。

属性(2)说明，任何子树根节点处的元素总是该子树中最大的元素。我们将属性(2)称为偏序树属性，或POT属性。

示例 5.28

图5-44展示了一棵具有10个元素的偏序树。在这里以及本节的其他部分中，我们都将用元素的优先级来表示它们，就像元素和它们的优先级是一回事那样。请注意，相等的元素可能出现在树中的不同层级。要说明偏序树属性在根节点得到满足，请注意，根节点处的元素18不小于其子节点处的元素18和16。同样，可以验证在该树的每个内部节点处偏序树属性都成立。因此，图5-44是一棵偏序树。

偏序树为优先级队列提供了一种实用的抽象实现。简单地说，要执行deletemax操作，就要找到根节点，它肯定是最大的，并用底层的最右节点代替它。不过，这样做时，偏序树属性可能被破坏，因此必须还原偏序树属性，要让新放置在根节点处的元素“向下沉”，直到它到达合适的层次，使得它小于它的父节点，并且不小于它的子节点。要执行插入操作，就要在底层尽可能左的位置增加一个新的叶子节点，如果底层没有空位置，就要新添加一个层级，并将该节点放在新一层的左端。这样也可能对偏序树属性造成破坏，如果造成破坏，就要让新元素“向上冒”，直到它找到合适的位置。

图 5-44　有10个节点的偏序树

5.9.2　平衡偏序树和堆

如果偏序树除最下层之外的所有层级的节点全存在，而且最下层的叶子节点尽可能集中在左侧，那么这样的偏序树就是平衡的。这一条件说明，如果该树有n 个节点，那么从根节点到任何节点的路径都不可能比log2n 长。图5-44中的树就是平衡偏序树。

平衡偏序树可以用称为堆的数组数据结构实现，这种数据结构提供了一种迅速、紧凑的优先级队列ADT实现。堆就是对元素下标有着特殊解释的数组A。首先从A[1]中的根节点开始，并未使用A[0]。在根节点之后，各层级依次出现。在同一层级中，节点按照从左到右的顺序排列。

因此，根节点的左子节点是在A[2]中，而根节点的右子节点在A[3]中。一般而言，A[i ]处节点的左子节点在A[2i ]中，而其右子节点在A[2i+1]中，如果这些子节点在偏序树中都存在的话。这种树的平衡性质使这种表示成为可能。这些元素的偏序树属性说明，如果A[i ]有两个子节点，那么A[i ]不小于A[2i ]和A[2i+1]，如果A[i ]只有一个子节点，那么A[i ]不小于A[2i ]。

图 5-45　图5-44对应的堆

实现的层次

对词典和优先级队列这两种ADT进行比较，并注意到每种情况下只给出了一种抽象实现以及对应该抽象实现的一种数据结构，这样做是很有意义的。每种ADT都有其他的抽象实现，而每种抽象实现也都有其他的数据结构。之前已经说过，在本书随后的内容中还将讨论词典的其他抽象实现，比如散列表，而且在5.9节的习题中表示过，二叉查找树对优先级队列而言也是种合适的抽象实现。下表总结了目前为止我们对词典和优先级队列的抽象实现及数据结构的了解。

ADT	抽象实现	数据结构
词典	二叉查找树	左子节点右子节点结构
优先级队列	平衡偏序树	堆

示例 5.29

表示图5-44所示平衡偏序树的堆如图5-45所示。例如，A[4]存放着值9，这一数组元素表示图5-44中根节点的左子节点的左子节点。而该节点的子节点则在A[8]和A[9]中。它们的元素分别是3和7，都不大于9，正如偏序树属性所要求的。数组元素A[5]对应着根节点左子节点的右子节点，它的左子节点在A[10]的位置。它可以有存放在A[11]中的右子节点，但图5-44中的偏序树只有10个元素，所以A[11]并不是该堆的一部分。

尽管这里展示的树节点和数组元素似乎就只是优先级本身，但原则上讲树节点或数组中出现的是完整的记录。正如我们将要看到的，在偏序树或其堆表示的父子节点间要进行很多元素交换。因此，如果数组元素是指向表示优先级队列中各对象的记录的指针，并将这些记录存储在堆“之外”的另一个数组中，就会更有效率。这样就可以在不调整记录本身的情况下直接对指针进行交换。

5.9.3　优先级队列操作在堆上的执行

在5.9节和5.10节中，会用全局整数数组A[1..MAX]表示堆。这里假设元素都是整数，而且都等于它们的优先级。当元素是记录时，可将指向记录的指针存储在数组中，并根据记录中的某个字段来确定元素的优先级。

假设有一个满足偏序树属性的具有n-1个元素的堆，我们要向A[n]中添加第n 个元素。偏序树属性在各处都继续成立，除了在A[n]和它的父节点间可能有例外。因此，如果A[n]大于其父节点位置的元素A[n/2]，就必须交换这些元素。而A[n/2]与其父节点间也可能违背偏序树属性。如果这样的话，就要让新元素递归地“冒泡”，直到它到达父节点有一个更大元素的位置，或是到达根节点位置。

执行这一操作的C语言函数bubbleUp如图5-46所示。它使用swap(A,i,j)函数交换A[i ]和A[ j ]处的元素，该函数也是在图5-46中定义的。bubbleUp的操作很简单。给定表示节点的参数i，它表示的节点与其父节点有可能违背偏序树属性，测试是否有i =1，也就是测试是否为根节点，在根节点的话就不会破坏偏序树属性。如果不是，则测试A[i ]是否大于其父节点处的元素；如果是，就在其父节点处递归地调用bubbleUp，交换A[i ]与其父节点。

void swap(int A[], int i, int j){
    int temp;

    temp = A[i];
    A[i] = A[j];
    A[j] = temp;}void bubbleUp(int A[], int i){
    if (i > 1 && A[i] > A[i/2]) {
        swap(A, i, i/2);
        bubbleUp(A, i/2);
    }}复制代码

图 5-46　swap函数交换数组元素，而bubbleUp函数则将堆中的新元素推到它的右侧位置

承德400电话申请开通【承德企业网站建设】承德微信公众号小程序开发运营价格、承德微信公众号APP软件客户端设计运营、承德网页页面设计公司费用、承德公司网站制作方案流程改版维护大概需要多少钱