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

Question

在索引中，我们除了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，而只是新建立了一个索引数组。

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

Answer 1

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

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

• 提问者 liuyubobobo #1

  大赞“索引堆是一个逻辑上的堆”这句话，理解的很透彻！：）

Answer 2

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%。