当前课程知识点：数据结构（Data Structures） > 3. Tree > 3.7 Introduction of Heap > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
各位同学大家好
接下来我们将学习到二叉树的
另外一个特殊应用 堆
我们先来看一下堆的定义
所谓的堆指的是一种具有下面的堆性质的
所谓的堆性质
指的是树上的每个结点它的取值
和它的孩子结点之间存在某些特殊的关系
其中一种堆的性质是指
树里面的每个结点
它的值都要小于或者等于
它的所有孩子的取值
具有这样性质的完全二叉树
我们把它称为叫小顶堆 Min-heap
顾名思义就是在上面的元素
是比较小的元素
根据这幅图中
给出的是一个小顶堆的例子
很显然 在树根位置里面
我们存放的是整个堆中最小的元素
另外一种堆的性质是指
每一个结点它的值要大于或者等于
它的孩子的取值
那么具有这个性质的完全二叉树
我们称为叫大顶堆
在右面这个图中所展示的
是一个大顶堆的例子
在这里面比较大的元素
是处于离树根比较近的位置
其中树根结点它的值是最大的
基于堆的结构
我们可以比较容易获得一组元素的最值
比如在这个图中它是一个大顶堆
那么最大值就是处于堆顶的位置 96
而当我们把这个堆顶的元素拿掉的时候
如果我们有办法可以很高效地
把剩下的元素重新调整成为一个大顶堆
那么我们又可以轻易地获得
剩下元素里面的最大值83
这个过程可以持续不断地做下去
我们就可以比较高效地
去获得在整个堆中最大的K个数据元素
同样的对小顶堆
我们也可以很高效地去获得
最小的K个元素
下面我们来看一下堆的实现
堆是一种完全二叉树
所以我们可以采用数组来去实现它
我们可以把堆里面的元素
从上到下 从左往右
依次地存储在数组中
而堆中的元素之间的关系
可以通过一组数学公式来进行计算
给定任何一个结点
我们都可以很容易地去找到它的父亲
以及它的孩子
下面我们来看一下具体的类实现
我们这里定义了一个maxHeap类
因为我们是基于数组去实现它的
所以在类里面有一个核心的数据成员
就是一个数组Heap
除了Heap之外
我们还定义了两个辅助的属性
一个是数组的大小size
以及在堆里面的数据元素的个数n
通过这些简单的属性成员
我们就可以去刻画一个堆的基本存储方式
另外为了去实现堆中的结点之间的关系
我们可以实现下面的一组基本操作
首先是左孩子关系操作 leftchild
这个函数的输入参数
是某个结点它的数组下标pos
我们知道对于一个
存放在pos位置上的结点来说
它的左孩子是存放在2×pos+1这个位置
因此leftchild这个函数
我们就返回2×pos+1
另外相似的右孩子关系操作
它会返回2×pos+2
这里我们还看到parent函数
它返回的是某个结点的父亲的位置
根据公式我们可以算出来
父亲所在的位置是(post-1)/2
最后我们可以定义一个isLeaf函数
用来去判断给定的一个结点
它是否是Yes结点
我们知道对于存放在pos位置的结点来说
它的左孩子如果存在的话
它应该存放在2×pos+1这个位置
那么我们也知道
叶子它是没有孩子的
因此它的2×pos+1这个位置
应该不属于0到n的这个合理的范围
所以我们会得到
2×pos+1>=n
那么我们通过一个不等式的变换会得到
pos>=n/2
所以我们要判断一个结点
它是否是叶子结点
我们只需要去判断它的pos
是不是大于等于n/2
另外这个pos
还要必须符合一个合理的下标取值范围
所以同时它要满足pos 现在我们已经学习了一些堆的存储结构 以及基本操作 在后面的章节中 我们将进一步地学习到 关于堆的更多操作 好的 我们这节课就学习到这里 下节课我们再见
-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
