当前课程知识点：数据结构（Data Structures） > 3. Tree > 3.9 Operations on Heap > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学 大家好
接下来的这一节课中
我们将学习到
堆栈的一些常用的操作的实现
这里我们主要介绍的操作包括
删除操作以及插入操作
在后面的课程中
我们将以大顶堆作为例子来展开讲解
那么小顶堆的操作
它的实现原理是类似的
在这里面我们就不再去重复
前面我们已经学习到了
在大顶堆中最大的值
是处于堆的最顶部
所以当我们从堆中取出这个最大值之后
如果我们能有效地把剩下的元素
再次重新调整成为一个堆
那么我们就可以通过一系列反复的
取出 调整的工作
最终可以得到堆中最大的若干个元素
那么在这里面很关键的一点就是
取出最大的堆顶元素之后
那么整个堆应该如何去进行调整呢
下面我们来看这样的一个例子
在取出堆顶元素之后
堆顶的位置必须由
另外一个元素来进行代替
而在整个堆里面
最适合用来去替代这个堆顶元素的
就是最后这个叶子结点
因为如果将这个叶子结点去掉
也不会影响我们整个堆的构造
因此我们这里面第一步
就是要把堆顶的元素和最后的叶子
来进行交换
这样原来的堆顶的元素
随时可以被我们删除的位置
这个时候我们需要考虑
这次交换是不是会导致整个二叉树
不再满足堆的性质
我们来比较一下
交换前后整个二叉树结构的变化
首先树根发生了变化
但是树根的左子树和原来是保持一致的
所以左子树依然是一个堆
而右子树是原子树的一个子集
同样也满足堆的性质
所以唯一不太确定
是否满足堆性质的
就是这个树根结点
我们只需要对树根进行调整
我们在前面堆的构建中已经学习过
这种左右子树都是堆的前提下
调整树根的过程
我们适合采用筛选过程
也就是Sift down函数
我们通过对树根调用Sift down
就可以把整一棵树
重新调整成为一个堆
所以在这里我们简单总结一下整个过程
当我们删除堆顶的最大元素的时候
我们首先要把它
和最后的叶子结点进行交换
然后我们对堆顶元素
进行一个Sift down的调整
就可以完成整个堆的调整过程
我们下面来看一下具体的实现过程
我们把这个删除最大元素的过程
实现为一个removemax函数
函数的参数是一个引用参数it
用来记录删除的堆顶元素的值
首先我们需要判断一下
这个堆它是不是空的
这个n是堆的元素的个数
那么如果我们判断它是一个空堆
则直接返回false
不再进行删除
否则的话我们要将堆顶元素
也就是0号位置的元素
和最后一个结点
也就是n-1号位置的结点
把它们进行交换
这里的Swap函数
就是用来去实现
数组Heap中两个未知的元素互换
其中第二个位置是--n
它的值就是n-1
同时--n它有一个副作用
它会让n的值减少1
这是由于堆中的元素减少了一个
所以n的值要减少1
接下来如果堆没有变成空堆
那么我们就要对堆顶的元素
也就是0号位置的元素调用siftdown
从而进行堆的调整
最后我们要把交换到末尾的
原来的堆顶元素的值记录下来
然后我们整个函数就可以成功返回了
这个函数它的运行复杂度
取决于其中最复杂的
Sift down函数的调用
由于Sift down函数
它的时间代价是Θ(log n)
所以removemax函数
它的时间代价也是Θ(log n)
下面我们来学习堆的另外一个常见的操作
插入操作的实现
在大顶堆中我们要插入一个结点的时候
我们要把它放到一个对全局的结构
影响最小的位置上面
从而能减少调整的复杂度
因为我们这个堆是用数组来实现的
所以最方便去放置新元素的位置
应该是数组的末尾的位置
这样相当于给原来的二叉树
添加了一个处在最后位置的叶子结点
添加完毕之后
我们就要开始去确认堆的性质
是否受到了破坏
我们主要是检查新加入的结点9
和父亲结点它们之间的关系
在这个例子中
因为是大顶堆
所以根据堆的性质
孩子结点必须要小于等于父亲结点
所以如果新加入的这个结点
它的值是小于等于它的父亲的话
那么就说明满足堆的性质
不需要进行更多的调整
否则如果比父亲大
那么我们就要把它和父亲进行交换
比如这里
9是要比它的父亲6要来得大的
所以我们要进行交换
那么这个时候是否已经满足堆的性质了呢
我们还需要进一步的把结点9
和它的父亲进行比较
只要我们发现它是比父亲大的
就要持续地进行交换
这个过程只要9还有父亲结点
就必须不断地进行
直到这个9是小于等于它的父亲
那么我们这个堆的性质就满足了
就可以停止交换
我们来看一下具体的代码实现
这里实现的insert函数
它有一个参数value
是用来去记录我们要插入的
数据元素的值
我们首先要判断一下
看看存放堆的数组它是不是满的
这里我们判断的是数据元素的个数n
它是否大于等于数组的大小size
如果它是大于数组的size的话
说明这个数组已经满了
我们插入将直接返回失败
接下来我们首先要确定插入结点的位置
我们定义一个整数cur
来去记录插入的位置
因为我们要将新结点插入到堆的末尾
所以我们让cur指向堆的末尾的位置
也就是n号位置
同时我们这里面写的是n++
执行完了之后会让n加1
对应的是堆中的结点数目加1
然后我们要将新插入的结点的值
记录在cur它所指向的末尾位置上面
接下来我们用一个循环语句
来去实现堆的调整
在整个过程中
curr变量始终是指向插入结点的位置的
只要插入了结点
它所处在的位置不在树根的位置
并且是大于父亲结点
那么将不符合大堆顶的性质
我们就需要对它进行调整
所以在循环体中
我们把curr位置的结点
和它父亲位置的结点
也就是parent(curr)位置的结点
进行了一个对调
在完成对调操作之后
我们同时更新curr变量
让它对应插入结点的位置
这里的循环语句每执行一次
插入的结点就会和它的父亲位置的结点
交换一次
而这个结点的深度也会减少1
因此交换的次数
最多它不会超过整个堆的高度
而对于有n个结点的堆来说
它的高度我们可以通过计算
是Θ(log n)
所以这个循环语句它的时间复杂度
是Θ(log n)
那么整个插入算法它的复杂度
也是Θ(log n)
我们这节课就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
