索引堆及其优化

系统管理员 2024-03-16 20:54 79阅读 0赞

#### 一、概念及其介绍 ####

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

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

相较于堆，优点如下：

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

#### 二、适用说明 ####

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

#### 三、结构图示 ####

![5c8574a36b1af2bda3677cc64eba5964.png][]

我们需要对之前堆的代码实现进行改造，换成直接操作索引的思维。首先构造函数添加索引数组属性 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/runoob/heap/IndexMaxHeap.java 文件代码： ###

> package runoob.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)。

![810f01ba37b7467bb57edbcac6e513c1.png][]

有如下性质：

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

[5c8574a36b1af2bda3677cc64eba5964.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3fbc12d22cfa47d58928c0abf3147f30.png
[810f01ba37b7467bb57edbcac6e513c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/574a8e2f38bb44a09dfe2313e44bcf15.png