索引堆的实现与优化
在之前文章中记述了堆的实现(插入方式建堆、heapify方式建堆以及堆排序) 《 堆的实现及其应用 》 。今天来看看索引堆是个什么东西,对于我们所关心的这个数组而言,数组中的元素位置发生了改变。正是因为这些元素的位置发生了改变,我们才能将其构建为最大堆。 如果元素十分复杂的话,比如像每个位置上存的是一篇上万字的文章。那么交换它们之间的位置将产生大量的时间消耗。并且由于数组元素的位置在构建成堆之后发生了改变,那么我们就很难索引到它,很难去改变它。可以在每一个元素上再加上一个属性来表示原来的位置可以解决,但是这样的话,必须将这个数组遍历一下才能解决。针对以上问题,我们就需要引入索引堆(Index Heap)的概念。