数据结构与算法基础知识总结(图解数据结构堆的各种操作与算法)

在后台开发人员的面试中,有这么一个经典的题目,我们有一堆定时任务,每个任务都有执行时间,这堆定时任务还有可能会不停的增加,要求我们设计一个数据结构与算法来实现,这个题目的经典答案,就是优先队列,那么优先队列的原理是什么呢?不知道你有没有被问过这个问题,今天我们就来学习优先队列的底层原理,是一个基础数据结构,叫做堆(Heap),数据结构的堆跟内存堆栈的堆不是一回事,曾经面试一个同学,问他堆是一种什么样的数据结构,直接把内存堆栈的概念背诵出来了,真是让人可笑不得。

数据结构与算法基础知识总结(图解数据结构堆的各种操作与算法)(1)

我们直接开门见山,数据结构中堆(Heap)是什么东西呢?这里,通常,我们讲的堆(Heap)都是二叉堆,堆是一颗完全二叉树,如果一个堆的深度为h,那么从第一层开始有1个节点,第二层有2个节点,第三层有4个节点,直到第h-1层有2^(h-2)个节点。我们把下图这种父节点小于子节点的堆称之为小根堆,反之,父节点都大于子节点的堆称之为大根堆。

数据结构与算法基础知识总结(图解数据结构堆的各种操作与算法)(2)

数据结构堆(Heap)的最大作用就是用来排序!我们以小根堆为例(以下操作均已小根堆为例),查询小根堆里面最小的元素,直接取第一个元素即可,算法时间复杂度为O(1)。

我们需要注意的是,一个堆如果要删除某个元素,只支持删除最顶部的元素!在堆里面,左儿子跟右儿子大小是不确定的,这个是二叉堆跟二叉排序树的一个区别(在数据结构二叉排序树中,左儿子<本身<右儿子。后面我们再来介绍下二叉排序树)。在堆中,删除头部元素称之为Pop,那么堆里面删除一个元素的算法是什么样子的呢。

我们先把最底层,最右边的元素,移到第一个元素,然后跟两个儿子比较大小,与较小的儿子交换位置因为17比65,32都小,所以把32跟17交换位置。

数据结构与算法基础知识总结(图解数据结构堆的各种操作与算法)(3)

重复上面的算法,将32与23,45一起比较大小,23是三者之中最小,再次交换位置

数据结构与算法基础知识总结(图解数据结构堆的各种操作与算法)(4)

重复上面的算法,将32与53进行比较,发现大小一致,不用变化

数据结构与算法基础知识总结(图解数据结构堆的各种操作与算法)(5)

所以,我们可以把堆的Pop操作算法总结如下:跟最后一个元素交换,从树根开始,比较儿子节点,与最小的交换,直到没有儿子或者比儿子更小,算法复杂度为O(LogN)。

在堆中,插入一个元素是什么样子的呢?我们先把元素插到堆的末尾,每次都与父亲节点进行比较,如果比父亲比它小,就跟他交换位置例如下图,我们新增一个元素22,它先跟自己的父亲节点32进行比较。

数据结构与算法基础知识总结(图解数据结构堆的各种操作与算法)(6)

重复上述算法,22再与23进行比较,随后交换位置

数据结构与算法基础知识总结(图解数据结构堆的各种操作与算法)(7)

最后我们又得到新的小根堆,每次插入一个算法的时间复杂度为O(LogN)

数据结构与算法基础知识总结(图解数据结构堆的各种操作与算法)(8)

堆的操作就是这么简单,支持3种操作,堆顶元素,弹出堆顶元素Pop,插入新的元素Insert。他们的算法学会了么?算法与数据结构,需要我们不停地练习,才能够熟练掌握,我会经常收集各大公司地算法面试题,分享一下经典地解题思路,有兴趣地话可以关注下我,关注下我的专栏。同名公众号(沙茶敏碎碎念)

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页