请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

【多说两句】关于索引堆中的索引和数据

在索引中,我们除了data之外,还引入了indexes。data中存放原始数据,indexes中存放的是索引。这里要注意:无论是data数组中的元素,还是indexes数组中的元素,都不构成堆!是谁构成了堆?是下面的这个数组:

data[indexes[1]], data[indexes[2]], data[indexes[3]], ..., data[indexes[n]]

换句话说,我们可以这样理解indexes。将data中的元素组织成一个堆以后,把他们原先对应的序号依次取出来,构成的数组就是索引数组的内容。而data的内容再恢复回去,不要动。在索引堆中,我们可以看到,shiftUp和shiftDown操作只改变索引数组indexes的内容,而不去动data。data就静静地躺在那里,看indexes数组变来变去。最后真正要使用data的时候,只要用indexes相应的元素做索引,指向data就好了。

所以,我们的getMax函数是这样的:

Item getMax(){    
    assert( count > 0 );    
    return data[indexes[1]];    
}

看,永远取indexes数组第一个元素为索引所对应的那个data,真正改变的是indexes:)


如果我们真正理解了indexes和data的含义,我们就能再聊点儿程序设计思维上的话题了。难道这种思想只能用在索引堆上吗?当然不是!其实这种思想到处都可以使用。最典型的,排序算法!我们之前讲解排序算法,说排序算法的复杂度,大多是基于比较操作的。也就是说,我们说快速排序的时间复杂度是O(nlogn),是因为其比较操作的次数是nlogn这个级别的。但是,我们没有太去考虑交换操作。如果我们的数据特别特别沉,挪动数据的成本特别特别高,怎么办?我们就可以引入索引这个概念了。我们新建立一个索引数组,指向真正的待排序数据,比较的时候通过索引取得真正的数据进行比较,但是真正交换的时候,只进行索引的交换。嗯,数据静静地躺在那里,等待着被索引。索引仅仅是一个int,挪动的成本就太低了!是不是很酷?

感兴趣的同学,可以选择自己喜欢的排序算法,封装一个基于索引的排序方法。在设计的时候,注意要对用户屏蔽实现细节。换句话说,用户没必要知道其实你的排序算法没有动data,而只是新建立了一个索引数组。

这个思路听起来是不是很熟悉?我才不会告诉你设计数据库的底层算法经常使用这种思路呢:)

正在回答 回答被采纳积分+3

2回答

慕粉3197494 2017-04-01 17:45:58

谢谢bobo老师解答。我本来是要问,为什么索引堆的插入需要索引这个参数?假如堆的容量是15,已经存了9个,在插入一个直接分配索引10 不就好了嘛~为什么还要指定呢?现在明白了,在做插入的操作前是要去判断索引的合理性的,并且索引堆是一个逻辑上的堆。O(∩_∩)O


2 回复 有任何疑惑可以回复我~
  • 提问者 liuyubobobo #1
    大赞“索引堆是一个逻辑上的堆”这句话,理解的很透彻!:)
    回复 有任何疑惑可以回复我~ 2017-04-01 20:26:42
ATWJSW 2017-11-10 02:29:07

开脑洞了。leetcode #506 relative ranks 用Java原生的Sort(底层是merge sort)sort Pair(index,data)在40%, 用基于索引quick sort 3 ways直接排,达到95%。

1 回复 有任何疑惑可以回复我~

相似问题

登录后可查看更多问答,登录/注册

问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信