可以管理时间的二叉堆

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

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

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

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

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

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

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

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

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

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

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

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

删除操作

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

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

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

谦子

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

谦子

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

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

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

所以要继续下沉

此时下沉完毕

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

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

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

谦子

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

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

只见谦子又写了一段代码

leftIndex = 2*parentIndex;

rightIndex = 2*parentIndex+1;

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

谦子

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