手记

关于对最大索引堆和切分定理的理解

详细请看波波老师的《C++算法与数据结构》
如图所示:最大索引堆
可以假设index1 = x;index是个数组;1表示的是位置;x表示的是
index这个索引数组对应1位置上的索引值;这个索引值很重要;
它还有另一项功能就是反映data数组的位置===》data[x] = 最大值;
这个最大值就是目前数据中最大的数据;我们来看看最大索引堆的由来:
通过比较data这个数组里面的数据值(例如:data[b1] < data[b2]);
来确定索引值在索引数组index[]中的位置;
所以 index1 = x;这个位置上的索引值x不一定是最大的,但是x对应的
(data[index1] = data[x] = 最大值)data里面的数据值一定是最大的

综上所述:比较data值;确定 索引值 在索引数组中的 位置;


另外就是切分定理了;想表达的是:不管把这张图看成整张图还是分成俩张
图看;对切分定理都没有影响的;所以切分定理可以把这张图划分为俩个区域看;当成整张图看的话至少会经过“横切边“中的一条;把图当成俩部分看的话也会如此;

0人推荐
随时随地看视频
慕课网APP