Video在线视频

各位同学大家好

前面我们已经学习了堆的存储结构

下面我们将进一步学习到

堆的构造过程

前面我们学了堆的类的定义

其中核心元素就是一个数组Heap

基于这个数组

我们实现了堆中数据元素的存储

在这里我们给出的是

大顶堆maxheap的定义

至于小顶堆的定义也是类似的

下面我们来重点介绍一下

如何实现堆的构造

我们要去使用堆

那么就必须要了解

给定一组数据

我们如何把这组数据组织成为一个堆

从而让数组中的数据满足堆的性质

这个过程我们可以在堆的构造函数中

来去实现堆的构造

我们可以看到这里构造函数有三个参数

第一个是用来指向一个数组的指针h

在这个数组中存储了一组数据

第二个参数num

记录的是数组中的数据的个数

第三个参数max

是指数组的大小

在这个构造函数的开始

我们要对这些属性成员进行赋值

我们采用Heap来去记录数组的位置

用n来去记录数组中数据的个数

用size来去记录数组的大小

然后构造函数最主要的工作

就是要调整数组中的数据

使得他们满足堆的性质

为了实现这个调整

我们定义了一个buildHeap函数

来去实现堆的调整

这个函数将数组中的数据位置进行调整

使得它能满足堆的性质

下面我们通过一些例子

来看一下如何将一组元素

调整成为一个堆

在这里面初始化的时候

这个堆里面

这个数组里面一共有7个元素

在图中我们可以看到

这些数组我们可以把它对应成为

一个完全二叉树

我们可以通过一系列的元素交换

将这个完全二叉树调整成为一个大顶堆

那我们根据大顶堆的性质

任何一个结点的值

都要比它的孩子要大

所以我们可以通过检查这棵二叉树上面

不满足堆性质的结点对

然后把它们进行对调调整

从而把二叉树调整成为一个大顶堆

比如在这个例子里面

数据元素2和4

它们的关系是不满足大顶堆的性质的

所以我们可以把它们进行对调

对调4和1的位置

对调2和1的位置

5和2的位置 5和4的位置

7和3的位置 7和5的位置

6和5的位置

总共我们经过了8次对调调整

最终得到了一个大顶堆

当然这个对调方案它不是唯一的

这个时候我们就需要思考

如何才能够最为有效 有序地

完成堆的构建

一般来说要让事情完成的比较有效

就必须要有一个有序的过程

一个自底向上构建堆的方法

有序有效地完成堆的构建

那我们可以分成以下几个步骤来完成

首先给定一个完全二叉树

我们会将树根的左子树先调整为一个堆

然后第二步

我们会将树根的右子树调整为一个堆

我们再将整一棵树调整成一个堆

在这里前面两个步骤

都是一个递归调整的过程

将其中一个子树调整成为大顶堆

我们这里重点要看一下最后这个步骤

在图中我们给出了相应的例子

当我们树根的左子树和右子树

都已经是大顶堆的情况下

接下来的调整过程

就取决于这个树根结点

如果树根结点是大于等于下面的孩子结点

那么我们就可以停止调整

因为它已经满足了大顶堆的性质

否则的话如果树根结点的值

是小于任何一个孩子结点

那么就违反了大顶堆的性质

因此为了检测堆的性质

我们可以将树根和两个孩子之间的较大值

进行比较

如果树根比较小

那么我们就需要调整

在这个例子中

树根1这个结点

它的两个孩子的较大值是7

由于树根1是小于这个结点的

所以不符合大顶堆的性质

因此我们可以将树根和这个较大的孩子

进行一次交换

这个时候替换下来的树根结点的值

将大于等于孩子的值

从而满足大顶堆的性质

那么针对替换下来的树根结点1

还需要继续地和它的孩子

进行进一步的比较

如果比较大的孩子结点的值

要比树根的要小

那么还要继续进行替换

这个比较和替换的过程

会从树根一直持续下来

直到整一棵树满足大顶堆的性质

整个过程中原树根结点

会从树根开始通过不断的比较 交换

直到停留到某个合适的位置

这整一个过程

我们称为筛选过程

英文叫做Sift down

我们接下来来看一下siftdown函数的实现

siftdown函数里面它有个参数pos

指的是树根结点在数组中的下标位置

siftdown的过程

就是将树根结点从上往下

调整到一个合适的位置的过程

在调整的过程中

我们要将pos位置的结点

和它的孩子结点进行比较

这里我们首先让j指向pos位置结点的

左孩子结点

让rc指向它的右孩子结点

如果这个右孩子是存在的

并且左孩子结点小于右孩子结点

那么我们就用j

来去指向右孩子结点

这样一来j始终指向的是

两个孩子里面的比较大的那个结点

所以我们这里将pos所指向的结点

和这个比较大的孩子进行比较

如果pos所指向的结点

要大于等于这个比较大的孩子

那么我们就说明它满足大顶堆的性质

我们就可以停止堆的调整

否则的话我们要将数据元素进行对调

这里的swap函数

就是将堆中数组中的pos位置的值

和j位置的值进行对调调整

当完成这个交换之后

我们需要去更换pos变量

让它重新指向交换之后的

根结点所在的位置

下面这个比较和对调调整的过程

是一个迭代持续的过程

我们需要将pos位置的结点

继续和它的孩子进行比较

所以我们需要一个循环语句

只要pos位置的结点

没有被调整到叶子的位置

那么这个循环将会持续下去

整个过程中有两个退出条件

一个是循环的退出条件

也就是pos位置的结点

被调整到叶子的位置

另外一个退出条件

是pos位置的结点

要大于等于它的孩子结点

满足堆的性质

那么这个循环也会退出

这个程序的循环语句执行的次数

等同于结点的交换次数

而我们知道交换的次数

在这里面是不会超过整棵树的高度的

对于结点数目为n的完全二叉树来说

它的高度是Θ(log n)

所以循环语句执行的次数也是Θ(log n)

也就是说siftdown函数的时间复杂度

是Θ(log n)

基于siftdown函数

我们就可以实现自底向上的

构建堆的过程

我们从最后的结点开始

逐个结点进行考察

对不满足堆性质的结点进行调整

那么在这里排到最后面的是叶子结点

因为叶子是没有孩子的

所以并没有违反堆的性质

不需要进行调整

所以我们首先从

最后一个中间结点开始进行调整

我们可以通过调用siftdown筛选过程

对这个结点进行调整

比如说在途中这个例子里面

2号结点我们需要对它进行调整

当然对2号结点

调用siftdown调整完毕之后

我们继续对前面的结点

进一步地进行调整

我们可以继续地对1号结点调用siftdown

然后再对0号结点调用siftdown

当我们对0号结点

也就是根结点调用siftdown之后

那么整一个二叉树

将会被我们调整成为一个大顶堆

所以我们这里归结一下

堆的构建过程

就是一个从后往前

对每一个中间结点

调用siftdown函数的过程

那么最终我们就可以得到一个大顶堆

相应地我们就可以去实现

这个堆的构建函数buildHeap

这个函数的实现过程其实比较简单

就是要去实现一个循环语句

对每一个中间结点

都去调用siftdown函数

那么其中最后的这个中间结点

它的数组下表是n/2-1

这是由于这个最后的中间结点

它是最后一个叶子结点

也就是n-1号结点的父亲

所以它的数组下标是

n-1-1然后对2整除

也就是n/2-1

所以for循环我们将从最后一个中间结点

n/2-1这个位置

一直到树根结点0号位置

对每一个中间结点

都去调用这个siftdown函数

最后我们就可以完成堆的调整

从而我们得到一个大顶堆

最后我们来分析一下堆的构建函数

buildHeap函数它的代价

我们可以看到堆的构建过程中

主要计算时间都消耗在树上的结点

相互之间比较以及交换

那么我们来分析一下堆的构建过程

整个过程中结点的比较和交换的次数

我们对这样的一棵二叉树

来进行逐层分析

由于buildHeap的函数

是从后往前进行堆的调整

所以我们先看最下层这个叶子结点

对这一层的结点我们是不需要调整的

所以对调交换的次数是0

那么对倒数第二层的结点来说

每一个结点最多会发生一次比较和交换

而这一层结点的数目

我们是可以证明约等于

结点总数的四分之一

也就是n/4

所以在这一层上

结点的比较和交换的总数是1×n/4

而对于倒数第三层的结点来说

每一个结点最多会发生两次比较和交换

而这一层的结点数目是n/8

所以在这一层上面

结点的比较交换的总数是2×n/8

如果我们对所有的层都进行编号

用i来去表示层的编号

那被每一层上面结点交换的总次数

我们都可以统一地表达成为

(i-1)n/2^i

所以整一棵树上面

结点比较和交换的总次数

我们可以归结为这样的一个求和公式

根据Θ的定义

我们最终可以得到这个总代价是Θ(n)

好的 我们这节课讲到这里