优化的索引堆基础实现
data - indexes - reverse 之间的关系.png
- 多了一个
reverse数组，reverse[i] = x的含义是：索引i对应的元素在indexes中的位置； -
indexes[i] = x的含义是：在indexes的i号位置存储的值x是指向data中x号位置存储的元素，而数组indexes是个堆，从几何的角度理解会更容易，纯用概念表述不太容易表述明白； - 重要性质：
-
reverse[indexes[i]] = i; -
indexes[reverse[x]] = x; -
indexes[i] = x;
reverse[x] = i;
-
- 初始时
reverse中的每个值都为 0；
public class IndexMaxHeap<Item extends Comparable> {
protected Item[] data; // 最大索引堆中的数据
protected int[] indexes; // 其中的值“指向” data 中存储的“重元素”
protected int[] reverse; // 最大索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置
protected int count;
protected int capacity;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public IndexMaxHeap(int capacity){
data = (Item[])new Comparable[capacity+1];
indexes = new int[capacity+1];
reverse = new int[capacity+1];
for( int i = 0 ; i <= capacity ; i ++ )
reverse[i] = 0;
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, Item item){
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
// 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。
assert !contain(i);
i += 1;
data[i] = item;
indexes[count+1] = i;
reverse[i] = count + 1;
count ++;
shiftUp(count);
}
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
private void shiftUp(int k){
while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}
// 交换索引堆中的索引i和j
// 由于有了反向索引reverse数组，
// indexes数组发生改变以后， 相应的就需要维护reverse数组
private void swapIndexes(int i, int j){
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
reverse[indexes[i]] = i;
reverse[indexes[j]] = j;
}
// 看索引i所在的位置是否存在元素
boolean contain( int i ){
assert i + 1 >= 1 && i + 1 <= capacity;
return reverse[i+1] != 0;
}
取出堆顶元素并下沉
// 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
public Item extractMax(){
assert count > 0;
Item ret = data[indexes[1]];
swapIndexes( 1 , count );
reverse[indexes[count]] = 0;
count --;
shiftDown(1);
return ret;
}
// -索引堆中, 数据之间的比较根据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;
}
}
从最大索引堆中取出堆顶元素的索引
// 从最大索引堆中取出堆顶元素的索引
public int extractMaxIndex(){
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes( 1 , count );
reverse[indexes[count]] = 0;
count --;
shiftDown(1);
return ret;
}
获取最大索引堆中的堆顶元素
// 获取最大索引堆中的堆顶元素
public Item getMax(){
assert count > 0;
return data[indexes[1]];
}
获取最大索引堆中的堆顶元素的索引
// 获取最大索引堆中的堆顶元素的索引
public int getMaxIndex(){
assert count > 0;
return indexes[1]-1;
}
获取最大索引堆中索引为 i 的元素
// 获取最大索引堆中索引为i的元素
public Item getItem( int i ){
assert contain(i);
return data[i+1];
}
将最大索引堆中索引为 i 的元素修改为 newItem
// 将最大索引堆中索引为i的元素修改为newItem
public void change( int i , Item newItem ){
assert contain(i);
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;
// }
// 有了 reverse 之后,
// 我们可以非常简单的通过reverse直接定位索引i在indexes中的位置
shiftUp( reverse[i] );
shiftDown( reverse[i] );
}
