索引堆及其优化

精华

小牛编辑

151浏览

2023-03-14

一、概念及其介绍

索引堆是对堆这个数据结构的优化。

索引堆使用了一个新的 int 类型的数组，用于存放索引信息。

相较于堆，优点如下：

优化了交换元素的消耗。
加入的数据位置固定，方便寻找。

二、适用说明

如果堆中存储的元素较大，那么进行交换就要消耗大量的时间，这个时候可以用索引堆的数据结构进行替代，堆中存储的是数组的索引，我们相应操作的是索引。

三、结构图示

我们需要对之前堆的代码实现进行改造，换成直接操作索引的思维。首先构造函数添加索引数组属性 indexes。

protected T [ ] data ; // 最大索引堆中的数据
protected int [ ] indexes ; // 最大索引堆中的索引
protected int count ;
protected int capacity ;

相应构造函数调整为，添加初始化索引数组。

...
public IndexMaxHeap ( int capacity ) {
data = (T [ ] ) new Comparable [capacity + 1 ] ;
indexes = new int [capacity + 1 ] ;
count = 0 ;
this. capacity = capacity ;
}
...

调整插入操作，indexes 数组中添加的元素是真实 data 数组的索引 indexes[count+1] = i。

...
// 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
// 传入的i对用户而言,是从0索引的
public void insert ( int i, Item item ) {
assert count + 1 <= capacity ;
assert i + 1 >= 1 && i + 1 <= capacity ;
i += 1 ;
data [i ] = item ;
indexes [count + 1 ] = i ;
count ++;
shiftUp (count ) ;
}
...

调整 shift up 操作：比较的是 data 数组中父节点数据的大小，所以需要表示为 data[index[k/2]] < data[indexs[k]]，交换 index 数组的索引，对 data 数组不产生任何变动，shift down 同理。

...
//k是堆的索引
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftUp ( int k ) {

while ( k > 1 && data [indexes [k / 2 ] ]. compareTo (data [indexes [k ] ] ) < 0 ) {
swapIndexes (k, k / 2 ) ;
k /= 2 ;
}
}
...

从索引堆中取出元素，对大元素为根元素 data[index[1]] 中的数据，然后再交换索引位置进行 shift down 操作。

...
public T extractMax ( ) {
assert count > 0 ;
T ret = data [indexes [ 1 ] ] ;
swapIndexes ( 1 , count ) ;
count --;
shiftDown ( 1 ) ;
return ret ;
}
...

也可以直接取出最大值的 data 数组索引值

...
// 从最大索引堆中取出堆顶元素的索引
public int extractMaxIndex ( ) {
assert count > 0 ;
int ret = indexes [ 1 ] - 1 ;
swapIndexes ( 1 , count ) ;
count --;
shiftDown ( 1 ) ;
return ret ;
}
...

修改索引位置数据

...
// 将最大索引堆中索引为i的元素修改为newItem
public void change ( int i , Item newItem ) {
i += 1 ;
data [i ] = newItem ;
// 找到indexes[j] = i, j表示data[i]在堆中的位置
// 之后shiftUp(j), 再shiftDown(j)
for ( int j = 1 ; j <= count ; j ++ )
if ( indexes [j ] == i ) {
shiftUp (j ) ;
shiftDown (j ) ;
return ;
}
}
...

四、Java 实例代码

src/heap/IndexMaxHeap.java 文件代码：

package heap ;

import java.util.Arrays ;

/**
* 索引堆
*/
// 最大索引堆，思路：元素比较的是data数据,元素交换的是索引
public class IndexMaxHeap <T extends Comparable > {

protected T [ ] data ; // 最大索引堆中的数据
protected int [ ] indexes ; // 最大索引堆中的索引
protected int count ;
protected int capacity ;

// 构造函数, 构造一个空堆, 可容纳capacity个元素
public IndexMaxHeap ( int capacity ) {
data = (T [ ] ) new Comparable [capacity + 1 ] ;
indexes = new int [capacity + 1 ] ;
count = 0 ;
this. capacity = capacity ;
}

// 返回索引堆中的元素个数
public int size ( ) {
return count ;
}

// 返回一个布尔值, 表示索引堆中是否为空
public boolean isEmpty ( ) {
return count == 0 ;
}

// 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
// 传入的i对用户而言,是从0索引的
public void insert ( int i, T item ) {

assert count + 1 <= capacity ;
assert i + 1 >= 1 && i + 1 <= capacity ;

i += 1 ;
data [i ] = item ;
indexes [count + 1 ] = i ;
count ++;

shiftUp (count ) ;
}

// 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
public T extractMax ( ) {
assert count > 0 ;

T ret = data [indexes [ 1 ] ] ;
swapIndexes ( 1 , count ) ;
count --;
shiftDown ( 1 ) ;

return ret ;
}

// 从最大索引堆中取出堆顶元素的索引
public int extractMaxIndex ( ) {
assert count > 0 ;

int ret = indexes [ 1 ] - 1 ;
swapIndexes ( 1 , count ) ;
count --;
shiftDown ( 1 ) ;

return ret ;
}

// 获取最大索引堆中的堆顶元素
public T getMax ( ) {
assert count > 0 ;
return data [indexes [ 1 ] ] ;
}

// 获取最大索引堆中的堆顶元素的索引
public int getMaxIndex ( ) {
assert count > 0 ;
return indexes [ 1 ] - 1 ;
}

// 获取最大索引堆中索引为i的元素
public T getItem ( int i ) {
assert i + 1 >= 1 && i + 1 <= capacity ;
return data [i + 1 ] ;
}

// 将最大索引堆中索引为i的元素修改为newItem
public void change ( int i , T newItem ) {
i += 1 ;
data [i ] = newItem ;
// 找到indexes[j] = i, j表示data[i]在堆中的位置
// 之后shiftUp(j), 再shiftDown(j)
for ( int j = 1 ; j <= count ; j ++ )
if ( indexes [j ] == i ) {
shiftUp (j ) ;
shiftDown (j ) ;
return ;
}
}

// 交换索引堆中的索引i和j
private void swapIndexes ( int i, int j ) {
int t = indexes [i ] ;
indexes [i ] = indexes [j ] ;
indexes [j ] = t ;
}

//********************
//* 最大索引堆核心辅助函数
//********************
//k是堆的索引
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftUp ( int k ) {

while ( k > 1 && data [indexes [k / 2 ] ]. compareTo (data [indexes [k ] ] ) < 0 ) {
swapIndexes (k, k / 2 ) ;
k /= 2 ;
}
}

// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftDown ( int k ) {

while ( 2 *k <= count ) {
int j = 2 *k ;
if ( j + 1 <= count && data [indexes [j + 1 ] ]. compareTo (data [indexes [j ] ] ) > 0 )
j ++;

if ( data [indexes [k ] ]. compareTo (data [indexes [j ] ] ) >= 0 )
break ;

swapIndexes (k, j ) ;
k = j ;
}
}

// 测试 IndexMaxHeap
public static void main ( String [ ] args ) {

int N = 1000000 ;
IndexMaxHeap <Integer > indexMaxHeap = new IndexMaxHeap <Integer > (N ) ;
for ( int i = 0 ; i < N ; i ++ )
indexMaxHeap. insert ( i , ( int ) ( Math. random ( ) *N ) ) ;

}
}

上述修改索引位置在查找索引位置我们使用了遍历，效率不高。我们还可以再优化一遍，维护一组 reverse[i] 数组，表示索引 i 在 indexes(堆) 中的位置，把查找的时间复杂度降为 O(1)。

有如下性质：

indexes[i] = j
reverse[j] = i

indexes[reverse[i]] = i
reverse[indexes[i]] = i