江苏龙网

  1. 主页 > 生活百科 > >

堆和二叉堆的实现和特性

二叉堆


堆和二叉堆的实现和特性

文章插图
作者公众号：一角钱技术（org_yijiaoqian）
堆 HeapHeap：可以迅速找到一堆数中的最大或者最小值的数据结构 。
将根节点最大的堆叫做大顶堆或大根堆，根节点最小的堆叫做小顶堆或小根堆 。
常见的堆有二叉堆、裴波那契堆等 。
堆本身是一个相对比较抽象的数据结构，那么它有具体的实现就分为二叉堆（二项堆、Binary）、裴波那契堆（基于树的） 。那么要实现的话一般面试来说或者经常会用的话就是二叉堆来实现，当然在工业级比较牛逼的应用都是裴波那契以及非常严格裴波那契 。裴波那契堆因为相对比较复杂，你可以不知道去怎么实现，但是你可以看它的时空复杂度更好，它的实现也是基于树，但是并不少二叉树而是多叉的 。
假设是大顶堆，则常见操作（API）:
  • find-max：O(1)
  • delete-max：O(logN)
  • insert(create)：O(logN) or O(1)
“堆” 这种数据结构为什么会有用？ 在很多线上中的情形经常会在使用，比如说经常一个数一个数的过来，同时还有从另外一边的化经常去删除一些数据，问你这些数据里面它最大值是多少？这里的最大值可能就代表优先级最高的结点或者是那个数需要你先处理的，比如说你的任务流里面随时你要拿出优先级最高的任务优先处理，那么这种数据结构就更加的好用 。
有些人可能会想我用数组来实现可不可以？或者是我直接排序可不可以？这里我们可以思考一下： 假设维护一个数组，每次有个新元素插入进来，你就需要把整个数组进行一次所谓的排序，这样的话时间复杂度就会是 nlogn，这样的话就是不够高效的，另外删除也可能比较麻烦，假设删除的是最大值或最小值在最后面的话还好，可以是 O(1) 的时间复杂度，但是如果在最前面的话，你就必须把整个数组最前面元素删除掉之后，把整个数组往前挪，这样时间复杂度又变差了 。
不同的实现比较：
https://en.wikipedia.org/wiki/Heap_(data_structure)
堆和二叉堆的实现和特性

文章插图
 
当你提到“堆” 的时候，不要默认认为是二叉堆，同时你要知道堆的实现又很多种，而二叉堆本身的话只是因为它相对比较容易实现，它的时间效率是堆里面算比较差的 。
二叉堆的性质通过完全二叉树来实现（注意：不是二叉搜索树）；
什么是完全二叉树？ 就是它的根和每一级结点都是满的，除了最下面一层叶子结点可能不满之外，其他上面结点都是满的 。
二叉堆（大顶）它满足下列性质：
  • 性质1：是一颗完全树；
  • 性质2：树中任意结点的值总数 >= 其子节点的值；

堆和二叉堆的实现和特性

文章插图
 
由于性质2，就可以保证根结点是最大的结点，所以我们访问最大值就直接返回这个根结点值 。这里思考一个问题：为什么要做成树的结构呢？其实就要方便，因为找最大值是O(1)了是满足的，但是问题是后续你要删除一个元素或者你要添加一个元素，怎么让这个操作高效，至少是 logn 的 。
二叉堆的实现细节
  1. 二叉堆一般都通过 “数组” 来实现
  2. 假设“第一个元素” 在数组中的索引为 0 的话，则父结点和子结点的位置关系如下：索引为 i 的左孩子的索引是 (2∗i+1)；索引为 i 的右孩子的索引是 (2∗i+2)；索引为 i 的父结点的索引是 floor((i−1)/2)；
因为把一个完全二叉树依次放到一维数组里面去，那么它的孩子和父亲之间的关系，就可以直接用下班的数学关系表示了 。

堆和二叉堆的实现和特性

文章插图
 
Insert 插入操作
  1. 新元素一律先插入到堆的尾部
  2. 依次向上调整整个堆的结构（一直到根即可） HeapifyUp
当这个堆要进行维护操作，也就是插入元素的时候以及你要删除元素的时候要怎么做？
例子：85 添加到二叉堆中
堆和二叉堆的实现和特性

文章插图
 
操作的细节分为两步：

上一篇：没有了

下一篇：Linux查看硬件信息超强命令sar，以及可视化工具ksar