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

Question

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

Answer 1

liuyubobobo 2017-11-09 14:13: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 #1

  刘老师，不好意思，我再问一下，你在课程上所讲的好像是不用维护原有数组数据的最大堆性质，只要满足IndexMap最大堆性质就行了，然后通过索引值找到对应的数组数据

• liuyubobobo 回复 提问者 慕UI5584032 #2

  最大索引堆中，索引排成了堆的形状，而不是数据排成了堆的形状。所以仔细观察，在最大索引堆中的代码，我们的swap只会交换index数组，而完全不交换data数组。但是，索引堆另外的一个好处就是可以通过索引获取数据（注意，在我咱们之前讲的堆中，只能拿到堆顶元素，对于堆中的其他元素一无所知），进而，我们也可以更改堆中的元素（而不仅仅是入堆和出堆两个操作），当更改了堆中的元素，就有可能打破堆的性质，此时需要相应的操作来维护堆的性质。

• 提问者 慕UI5584032 回复 liuyubobobo #3

  刘老师你没有理解我的意思,我的疑问在于:change(int i,Item newItem){
  	i+=1;
  	data[i] = newItem;(到这一步不是已经完成change方法的目的了嘛。。,同时change()方法也没有在index最大堆中增加或者其他破坏IndexMap最大堆性质的操作,你也说了不是数据排成了堆的形状，也就是不用维护数据的最大堆性质，那既然这样)
  	这一步for( int j = 1 ; j <= count ; j ++ )
    if( indexes[j] == i ){
   shiftUp(j);
   shiftDown(j);
   return;
   }程序代码的目的在哪。。
  }

点开查看后面2条评论