现在的位置: 首页 > 面试题 > 正文

索引堆及其优化

2022年01月10日 面试题 ⁄ 共 3536字 ⁄ 字号 暂无评论
博客主机

一、概念及其介绍

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

 

索引堆使用了一个新的 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 实例代码

源码包下载:Download

 

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

Wopus问答

【上篇】
【下篇】

Wopus问答

给我留言

留言无头像?


×