day12 二叉堆

在描述堆之前先看看一道思考题先，假设现在要求设计一种数据结果，用来存放整数，要求提供3个接口：

1.添加元素；2.获取最大值；3.删除最大值

你考虑可能有如下几种：

动态数组或者双向链表：

无序动态数组或链表

有序动态数组或者双向链表

有序动态数组或链表

BST

BST

复杂度分析

复杂度分析

但是有没有更优的数据结构呢？

可以考虑用堆去实现，堆获取最大值O(1),删除最大值:O(logn),添加元素O(logn)

另外注明的Top k问题也是可以用数据结构堆来解决的

堆(Heap)

堆是一种树状的数据结构（不要跟内存模型中的堆空间混淆），常见的堆实现有：

二叉堆(Binary Heap，完全二叉堆),多叉堆(D-heap,D-ary Heap)

索引堆(Index Heap),;二项堆(Binomial Heap) 斐波那契堆(Fibonacci Heap)等

堆有一个重要的性质：任意节点的值总是\geq 或者\leq 子节点的值

如果任意节点的值总是\geq 子节点的值，称为：最大堆，大根堆，大顶堆；如果任意节点的值总是\leq 子节点的值，称为：最小堆，小根堆，小顶堆

堆的基本接口设计

int size();//元素的数量

boolean isEmpty();//是否为空

void clear();//清空

void add(E element); //添加元素

E get();//获得对顶元素

E remove();//删除对顶元素

E replace(E element);// 删除堆顶元素的同时插入一个新元素

二叉堆(Binary Heap)

二叉堆的逻辑结构就是一颗完全二叉树，所以也叫完全二叉堆，鉴于完全二叉树的一些特性，二叉堆的底层(物理结构)一般用数组实现即可；

二叉堆

索引i的规律(n 是元素数量）

如果i=0，那么它是根节点;

如果i > 0,它的父节点的索引为floor((i - 1)/2);

如果2i + 1 \leq  n - 1,它的左子节点的索引为2i + 1；

如果2i + 1 > n - 1,它无子节点；

如果2i + 2 \leq  n -1,它的右子节点的索引为2i + 2;

如果2i + 2 > n -1 ,它无右子节点

从上面的图可以看出，获取二叉堆的最大值非常简单

最大值获取

最大值

元素添加(最大堆元素添加)

示例图如下：


上滤1
上滤2
上滤3
上滤4

添加总结

循环执行操作，例如上图的80，如果node > 父节点（与父节点交换位置）；如果node \leq  父节点，或者node没有父节点（退出循环），时间复杂度是O(logn)

源码示例图：

添加元素方法
shiftup

可以看到shiftup方法实现有两个，第一个方法就是对应着前面展示的示例提图，这种情况复杂度大概是3 * O(logn)，因为有3次交换，而方法2对应的是下面的展示图，复杂度可以优化到1 * O(logn) + 1


shiftup1
shiftup2
shift3
shiftup4
shiftup5

方法二相对于方法一的不同就是方法二在记录着最终需要赋值元素的索引，跳出外循环之后才赋值，这也是优化的关键点所在；到这里添加元素就讲完了，接下来看看删除。

最大堆删除

示例图：


siftdown

最大堆删除总结

1.用最后一个节点去覆盖根节点

2.删除最后一个节点

3.循环执行以下操作(图中的43简称为node),如果node < 最大的子节点，与最大的子节点交换位置，如果node\geq 最大的子节点，或者node没有子节点，退出循环；

这个过程叫做下滤(Sift Down),时间复杂度:O(logn)

删除代码图：

remove
siftDown

最大堆-批量建堆(Heapify)

有两种方法：1.自上而下的上滤；2.自下而上的下滤

1.自上而下的上滤

自上而下的上滤

2.自下而上的下滤


自下而上的下滤

代码实现图：

heapify

最大堆-批量建堆-效率对比

效率对比图

所有节点的深度之和

仅仅是叶子节点，就有近n/2个，而且每一个叶子节点的深度都是O(logn)级别的，因此在叶子这一块就达到了O(nlogn)级别，O(nlogn)的时间复杂度足以利用排序算法对所有节点进行全排序

所有节点的高度之和

假设是满树，节点总个数为n，数高为h,那么n = 2^h - 1,假设所有节点的树高之和H(n) = 2^0*(h-0) + 2^1 *(h-1)+......2^{h-1} *[h-(h-1)];

H(n) = h * (2^0 + 2^1 + 2^2+....2^{h-1} )-[1*2^1 + 2 * 2^2 + (h-1)*2^{h-1} )];

H(n)=h*(2^{h-1} ) -[(h-2)*2^h +2];

H(n)=h*2^h -h-h*2^h +2^{h+1} -2;

H(n)=2^{h+1} -h -2=2*(2^h -1)-h=2n-\log_2 {(n+1)}  = O(n);

公式推导过程：

S(h)=1*2^1+2*2^2+3*2^3+....+(h-2)*2^(h-2) + (h-1)*2^(h-1)

2S(h)=1*2^2+2*2^3+3*2^4+....+(h-2)*2^(h-1) + (h-1)*2^h

S(h)-2S(h)=[2^1+2^2+2^3+...2^(h-1)]-(h-1)*2^h=(2^h-2)-(h-1)*2^h

S(h)=(h-1)*2^h-(2^h-2)=(h-2)*2^h+2;

Top K问题

从n个整数中，找出最大的前k个数(k远远小于n)，如果使用排序算法进行全排序，需要O(nlogn)的时间复杂度，但是如果使用二叉堆来解决的话，可以使用O(nlogk)的时间复杂度来解决

1.新建一个小顶堆

2.扫描n个整数，先将遍历到前k个数组放入堆中，从第k+1个数开始，如果大于堆顶元素，就使用replace操作（删除堆顶元素，将k+1个数添加到堆中），扫描完毕后，堆中剩下的就是最大的前k个数

如果是找出最小的前k个数呢？

使用大顶堆，如果小于堆顶元素，就使用replace操作

demo

到这里，二叉堆介绍完毕，如果有问题，欢迎留言哈!

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 堆排序和优先队列
    堆是一棵满足一定性质的二叉树，具体的讲堆具有如下性质：父节点的键值总是不大于它的孩子节点的键值（小顶堆）, 堆可以...
    9527Roy阅读 3,978评论 0赞 0
  • 优先队列——堆
    0.目录 1.优先队列ADT 2.几种实现 3.二叉堆 4.d-堆 5.左式堆 6.斜堆 7.二项队列 8.斐波那...
    王侦阅读 8,567评论 1赞 2
  • 【译】Swift算法俱乐部-堆
    本文是对 Swift Algorithm Club 翻译的一篇文章。Swift Algorithm Club是 r...
    Andy_Ron阅读 4,610评论 0赞 5
  • 数据结构基础概念篇
    一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这...
    Winterfell_Z阅读 11,497评论 0赞 13
  • 经典排序算法在python上的实现
    排序算法是算法中的基础，也是面试重点。现利用Python语言实现了经典的排序算法并且做出一定的总结。也是帮助自己记...
    Vivus阅读 1,189评论 0赞 0

友情链接更多精彩内容