可以管理时间的二叉堆

面试官:写一个堆排吧 我心想:堆排是什么鬼

理解堆排,首先要理解二叉堆。理解了二叉堆的“下沉”操作,基本上就可以理解堆排了。今天我们来看一看什么是堆,以及堆的一般操作

然后我把优先级存入一个无序数组里,取出的时候遍历数组一边,找出最小值,插入的时候直接插到集合末尾

这样,父子关系就可以用下标来表示了,显然,在k下标处的节点的左孩子一定在2*k小标处,右孩子在2*k+1处

当你插入一个元素的时候,很有可能破坏堆的有序性

每个父节点的值小于等于其左右孩子的值被称为堆的有序性

另一种情况是大于等于也称之为堆的有序性

克随手画了一个插入操作破坏堆有序性的图

这个时候1成为了2的右孩子了,此时它比2小,还得继续交换

此时,整个插入过程就完成了

说完,克飞速地写出了上浮的代码

谦子暗自惊叹老师的代码功力

删除操作

插入操作已经给你演示过了,删除操作你来想想吧

谦子听完此话紧张的手心出汗,但还是硬着头皮想了想,突然灵光一现

我可以把堆顶的元素和堆的最后一个元素交换,然后逻辑上删除最后一个元素

谦子

这里我用一个heapSize变量记录堆中元素的个数,交换后heapSize减一

谦子

随后谦子画出了交换后的图

这样我就通过交换堆顶元素与最后一个元素和heapSize减一把堆顶元素删除了

这个时候堆顶元素9来到了它的左孩子处,但是此时它大于现在的左右孩子

所以要继续下沉

此时下沉完毕

很不错,完全正确,这就是堆下沉的整个操作,那你写一下这个操作的代码吧

谦子刚松了口气,谁知还要写代码,只见谦子想了想,写写擦擦好几遍最终写下了如下代码

我找出以要下沉节点为父节点和它的左右孩中值最小的节点,如果该节点是左右孩子其中一个,则下沉,否则不下沉

谦子

慧子解释道,并画了一个图

这个思路不错,那你的那个找出最小节点下标的函数(minIndex())是如何实现的?

只见谦子又写了一段代码

leftIndex = 2*parentIndex;

rightIndex = 2*parentIndex+1;

我用一个变量存储值最小节点的下标,先让左孩子和父节点比,将其中值小的节点的下标存入minIndex,然后让右孩子与刚才选出最小值的节点比,更新minIndex

谦子

看来以后得好好学数据结构与算法了,不然连时间都管理不好

原文发布于微信公众号 - 趣谈编程(gh_51e791ad9174)

原文发表时间:2017-12-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发技术

排序之堆排序

  本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中...

992
来自专栏Fundebug

代码面试需要知道的8种数据结构(附面试题及答案链接)

为了保证可读性,本文采用意译而非直译。另外,本文版权归原作者所有,翻译仅用于学习。

1557
来自专栏Java社区

Java开发者容易犯的十个错误

1252
来自专栏小狼的世界

Leetcode刷题记录:构建最大数二叉树

给定一个不含重复数字的数组,最大二叉树构建规则如下: 1、根是数组中最大的数字 2、左边的子树是最大数字左边的内容 3、右边的子树是最大数字右边的内容

1092
来自专栏为数不多的Android技巧

[译]厌倦了NullPointException?Optional拯救你!

有人说,当你处理过了空指针异常才真正成为一个Java开发者。抛开玩笑话不谈,空指针确实是很多bug的根源。Java SE 8引入了一个新的叫做java.util...

1222
来自专栏浪淘沙

Java学习day16---人际关系

1305
来自专栏Android机动车

数据结构学习笔记——栈

我们允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。

923
来自专栏码匠的流水账

使用kotlin改善java代码

本文只是举了kotlin可以改善java代码的几个例子,kotlin太强大了,目标是要替代java。其中很多设计可以看到scala的影子,但是黑魔法也比较多,学...

731
来自专栏linux驱动个人学习

Android系统的智能指针(轻量级指针、强指针和弱指针)的实现原理分析【转】

Android系统的运行时库层代码是用C++来编写的,用C++ 来写代码最容易出错的地方就是指针了,一旦使用不当,轻则造成内存泄漏,重则造成系统崩溃。不过系统为...

982
来自专栏林欣哲

HashMap解析

1163

扫码关注云+社区

领取腾讯云代金券