老师你好,关于本章change()的问题

来源：4-8 索引堆(Index Heap)

慕UI5584032

2017-11-09

索引堆change()的时候,在改变指定数组数值之后,IndexHeap已经是最大堆了,为什么还要多一步shiftUp,shiftDown,来满足最大堆得性质

写回答

1回答

liuyubobobo

2017-11-09

已采纳

因为change有可能破坏堆结构。

简单的例子，如果我们的最大堆是这样的（这里为了举例方便，index就是顺序的了）：

         (index=0) value = 100
        /                     \
(index=1)                      (index=2)
value= 90                       value=80

如果我们将index=1的元素修改为999，就变成了这样：

         (index=0) value = 100
        /                     \
(index=1)                      (index=2)
value= 999                      value=80

此时，它已经不再是一个最大堆，需要重新整理成最大堆。

慕UI5584032

谢谢刘老师的耐心讲解，辛苦了

2017-11-09

共5条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 2

回答 1

回答 2

回答 1