优化的索引堆基础实现

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] );
}