上往建站提供服务器空间服务商，百度快照排名，网站托管，百度推广运营,致力于设计外包服务与源代码定制开发，360推广，搜狗推广,增加网站的能见度及访问量提升网络营销的效果,主营：网站公司,百度推广公司电话,官网搭建服务,网站服务企业排名,服务器空间,英文域名等业务，专业团队服务，效果好。

张北微信公众号开发【张北网络推广】张北建站、张北网站维护、张北网页制作、张北微信小程序代运营公司

河北省张家口市张北县地处河北省西北部，内蒙古高原南缘的坝上地区，境域东西109公里，南北67公里，东南部与崇礼区交界，桦皮岭为全县最高点，海拔2128米；北、中部地势平坦，向西北渐低，安固里淖为最低点，海拔1300米。全县总面积4185平方公里，辖18个乡镇、366个行政村、1167个自然村，总人口37.2万人。居民以汉族为主，占总人口的98%，还有蒙古族、回族、满族等。张北县是离京津地区最近的高原地区，夏天气候凉爽是避暑胜地。

张北县被列为第一批国家新型城镇化综合试点地区。 [1]  2019年11月，入选第二批节水型社会建设达标县（区）名单。 [2]  2020年2月29日，退出贫困县序列，正式脱贫“摘帽”。 [3]  2020年12月，入选河北省数字乡村试点地区名单。

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函数则将堆中的新元素推到它的右侧位置

示例 5.30

假设有图5-45所示的堆，并向其添加了优先级为13的第11个元素。该元素会出现在A[11]中，就有了如下数组

调用bubbleUp(A,11)，对A[11]和A[5]进行比较，因为A[11]更大，所以必须交换这两个元素。也就是说A[5]和A[11]违背了偏序树属性。因此，数组就成了

调用bubbleUp(A,5)，对A[2]和A[5]进行比较，因为A[2]更大，所以不会违背偏序树属性，bubbleUp(A,5)不会进行任何操作。这样就已经恢复了该数组的偏序树属性。

现在介绍如何实现优先级队列的插入操作。设n 是优先级队列中当前的元素数，并假设数组A[1..n]已经满足偏序树属性。增加n，并将待插入的元素存储到新的A[n]中。最后，调用bubbleUp(A,n)。表示插入操作的代码如图5-47所示。参数x是待插入的元素，而参数pn是指向优先级队列当前大小的指针。请注意，n 必须按引用传递，也就是说，通过指向n 的指针传递，这样当n 增加时，改变才不只是在插入操作局部造成影响。这里省略了对n<MAX 的检查。

void insert(int A[], int x, int *pn){
    (*pn)++;
    A[*pn] = x;
    bubbleUp(A, *pn);}复制代码

图 5-47　在堆上实现的优先级队列插入操作

要实现优先级队列的deletemax操作，需要对堆或偏序树进行另一项操作，这次是让根节点处可能违背偏序树属性的元素向下沉。假设A[i ]可能违背偏序树属性，在它中的元素可能小于其子节点A[2i ]和A[2i+1]中的一个或两个。我们可以将其与其中一个子节点交换，不过一定要注意是与哪一个交换。如果与两个子节点中较大的那个交换，那么肯定不会在A[i]曾经的两个子节点间引入偏序树属性的破坏，因为较大的那个现在已经是较小那个的父节点了。

图5-48中的bubbleDown函数实现了这一操作。在选择了与A[i ]进行交换的子节点后，它会递归地调用自身，以消除新位置上的元素A[i ]（也就是现在的A[2i ]或A[2i+1]）与其新子节点之间可能存在的偏序树属性的破坏。参数n 是堆中的元素数，或者说是最后一个元素的下标。

这个函数有点棘手。如果A[i ]有两个子节点，就必须决定将其与哪个子节点交换，所以首先要在图5-48的第(1)行假设较大的子节点是A[2i ]。而如果右子节点存在（即child<n），并且右子节点更大，第(2)行的测试就会得到满足，并在第(3)行让child 成为A[i ]的右子节点。

在第(4)行有两项需要测试的内容。首先，A[i ]在该堆中有可能真的没有子节点。因此要通过检测是否有child≤n 来确定A[i ]是否为内部节点。第第二项测试是检测A[i ]是否小于A[child ]。如果两项条件都满足，那么在第(5)行就要将A[i ]与它较大的那个子节点交换，并在第(6)行递归地调用bubbleDown，如果有必要的话，就将违背偏序树属性的元素进一步向下压。

     void bubbleDown(int A[], int i, int n)
     {
         int child;(1)      child = 2*i;(2)      if (child < n && A[child+1] > A[child])(3)          ++child;(4)      if (child <= n && A[i] < A[child]) {(5)          swap(A, i, child);(6)          bubbleDown(A, child, n);
         }
     }复制代码

图 5-48　bubbleDown会将违背偏序树属性的元素压到合适的位置

可以按照图5-49所示的方式用bubbleDown实现优先级队列的deletemax操作。deletemax函数接受数组A 和指向堆中当前元素数n 的指针pn 作为参数。这里省略了对n>0的测试。

在第(1)行，将根节点处要删除的元素与最后的元素（在A[n]中）交换。技术上讲，应该返回删除的元素，不过，正如所看到的，将其放入不再属于该堆的A[n]也是可以的。

张北微信公众号开发【张北网络推广】张北建站、张北网站维护、张北网页制作、张北微信小程序代运营公司

上往建站提供搭建网站，域名注册，官网备案服务，网店详情页设计，企业网店，专业网络店铺管理运营全托管公司咨询电话，服务器空间，微信公众号托管，网页美工排版,致力于域名申请，竞价托管，软文推广，全网营销,提供标准级专业技术保障，了却后顾之忧,主营：虚拟主机，网站推广，百度竞价托管，网站建设，上网建站推广服务，网络公司有哪些等业务，专业团队服务，效果好。

服务热线：400-111-6878 手机微信同号:18118153152（各城市商务人员可上门服务）