问题描述

想要实现一个优先队列,我可以使劲往里丢东西(insert),也可以把最大的弹出来(delMax)

解法

概述

我就不假情假意的介绍一番用有序的数组或者链表来实现的方法了,不是丢东西慢,就是弹东西慢,最后还是用树的思想来解,树为啥这么牛逼呢。

先引入一个概念,”堆有序”, 就是说一个二叉树(最多只有两个叉叉的树),如果对于任何一个节点,都满足该节点不小于他的两个子节点的任意一个,那这个二叉树就是堆有序的,如果我们把值大成为屌的话,就是越往上越掉的感觉,类似你老板坐最上面,下面是左右护法,再下面是你。

然后从上往下一个个塞到数组里面,这个数组就是”二叉堆”,是堆有序的二叉树的一种表现形式,具体来说对于 index 是 k 的那个家伙,他的爸爸就是 k / 2(整数除法,舍弃小数),他的两个小弟就是 2k 和 2k + 1

术语

上浮(swim)

书上是叫 swim,为啥不叫 swim up 呢?

就是一个节点,如果发现他的父节点比他还小,那么就和他的父节点交换位置,一直到他合适的位置,那这个过程就是 上浮,重新构建了堆有序

下沉(sink)

就是一个节点,如果发现他的子节点有比他还小,那么就和他子节点最小那个交换位置,一直到他合适的位置,那这个过程就是 下沉,重新构建了堆有序,上浮的是跟父节点比,下沉是跟子节点比

我们来正式吃肉咯。

插入

怎插入呢(咳~咳~),就是把一个节点新增到最下面的一层,然后把他上浮到合适的位置,那插入就完成了,跟没插入的时候一样样的,都是堆有序,多么完美

选出最大

选最大值呢,就是把最高那个拿走,把最低的放到这个位置,然后先下沉到合适的位置,撤退之后依然是堆有序

构建堆

堆排序分两步,第一步是构建堆。一种暴力的方法是我们从前到后一个一个的节点上浮到合适的位置,遍历完节点就完成了树的构建,另外一种更好的做法是最后一层不管,从倒数第二层开始,每一个节点做下沉,这样用的次数就少很多

排序

第二步是排序,就是依次取出最大元素就好了, 思想跟选择排序一样,实现起来就快多了。