【数据结构与算法学习笔记十二】堆

今天我们来学习,学习一个数据结构之前,我们还是先来了解一下这个东西在干什么用的吧。相信大家都知道并用过有一个类,优先队列。很多优先队列的内部实现就是堆。此外,堆还可以用来排序,还可以进行一些算法的优化。我们后续有机会再继续介绍。

这不是一篇教程,只是根据我对堆的理解,总结一些性质。我们还是使用问答的形式。

第一,什么是堆?

数据结构中的堆跟平时我们讲的内存的堆还是有点区别的。数据结构中的堆其实是利用完全二叉树的结构来维护一组数据。

好了,怎么又引入一个概念了,什么是完全二叉树。

若设二叉树的深度为h,除第h层外,其它各层(1~h-1)的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是完全二叉树。

就像这样:

第二,堆的分类:

一般我们把堆分为大根堆小根堆也称最大堆,最小堆。顾名思义,就是堆的每个节点都大于它的子孙节点称为大根堆,堆的每个节点小于他的左右子孙节点称为小根堆。

注意到,在堆中,兄弟之间并没有大小关系,只跟父节点有大小关心。

第三,堆有哪些操作?

操作名称 描述 时间复杂度
Insert 插入一个新的 元素 Logn
top 大根堆最大的元素,小根堆最小的元素 1
Pop 弹出最大(小)的元素 Logn

是的,传统的堆只能有这3种操作,如果非要再加一个,那就是初始化。

第四,我们怎么实现一个堆?

因为堆是一颗完全二叉树,所以,我们可以用数组来实现一个堆。这里稍微讲一下为什么数组可以。估计很多人看了不懂,大家可以看第一张图,完全二叉树中,如果我们第一个结点以1开始,那么,对于每一个节点,如果它的下标为x,那么左儿子下标为2x右儿子下标为2x+1

在c++中,可以用stl库的,make_heap();pop_heap();push_heap();sort_heap()。

平时开发我们更经常使用基于堆开发的优先队列,如:

java的PriorityQueue,c++的priority_queue;在python中,可以设置queue的priority属性。

这里还是推荐大家手工用数组实现一下。

第五,堆怎么插入一个元素?

我们用一个小根堆来举例说明,首先我们把2插入末尾。下标为13。

13/2=6,他的父亲下标为6,我们发现a[13]

6/2 = 3, a[6]

插入一个新的元素的步骤可以总结为,将这个元素放到末尾,不停地与他的父亲比较。我们成这个操作为shift_up,上浮。

第六,堆怎么弹出最大(小)元素?

我们还是用上面那一个例子举例,初始状态为:

当我们pop出大根堆,这个时候我们将对堆顶跟最后一个元素交换。

紧接着我们自上一下,1开始,我们先比较它是否比两个儿子当中更小的那一个大,如果是,与那个儿子交换。

重复这个操作,

弹出一个元素的过程可以总结为,与最后一个元素交换,不断下沉。我们称之为shift_down

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注