heapsort heap( 三 )

16被添加最后一行的第一个空位。
不行的是，现在堆属性不满足，因为2在16的上面，我们需要将大的数字在上面（这是一个最大堆）
为了恢复堆属性，我们需要交换16和2。
现在还没有完成，因为10也比16小。我们继续交换我们的插入元素和它的父节点，直到它的父节点比它大或者我们到达树的顶部。这就是所谓的shift-up ，每一次插入操作后都需要进行。它将一个太大或者太小的数字“浮起”到树的顶部。
最后我们得到的堆：
现在每一个父节点都比它的子节点大。
我们将这个树中的(10)删除：
现在顶部有一个空的节点，怎么处理？
当插入节点的时候，我们将新的值返给数组的尾部。现在我们来做相反的事情：我们取出数组中的最后一个元素，将它放到树的顶部，然后再修复堆属性。
【heapsort heap】 现在来看怎么shift-down(1)。为了保持最大堆的堆属性，我们需要树的顶部是最大的数据。现在有两个数字可用于交换7和2。我们选择这两者中的较大者称为最大值放在树的顶部，所以交换7和1 ，现在树变成了：
继续堆化直到该节点没有任何子节点或者它比两个子节点都要大为止。对于我们的堆，我们只需要再有一次交换就恢复了堆属性：
绝大多数时候你需要删除的是堆的根节点，因为这就是堆的设计用途。
但是，删除任意节点也很有用。这是remove()的通用版本，它可能会使用到shiftDown和shiftUp。
我们还是用前面的例子，删除(7) :
[图片上传失败...(image-d46ac4-1534077058042)]
对应的数组是
你知道，移除一个元素会破坏最大堆或者最小堆属性。我们需要将删除的元素和最后一个元素交换：
最后一个元素就是我们需要返回的元素；然后调用removeLast()来将它删除。(1)比它的子节点小，所以需要shiftDown()来修复。
然而，shift down 不是我们要处理的唯一情况。也有可能我们需要 shift up 。考虑一下从下面的堆中删除(5)会发生什么：
现在(5)和(8)交换了。因为(8)比它的父节点大，我们需要shiftUp()。
stack 和heap都是堆积的意思，两者有区别吗在计算机语言中，stack
表示栈，heap表示堆，这是两个概念。
栈stack是计算机系统提供的具有后进先出特点的数据结构，
而堆heap是函数库提供的内部结构，为分配新内存空间服务的。
在日常英语中，二者都指堆积（动词）和一堆（名词），但是
heap
通常指杂乱的、呈小山状的一堆东西，如：Now，
the
house
is
a
heap
of
rubble（现在，房子成了一堆瓦砾）。
stack通常是整齐的一叠，指扁平物体叠放起来，如：a
neat
stack
of
dishes（整齐的一叠盘子）。

文章插图

heapsort heap( 三 )

秒懂生活扩展阅读