进击的堆：最大索引堆

文章图片存储在GitHub，网速不佳的朋友，请看《进击的堆：最大索引堆》 或者 来我的技术小站 godbmw.com

1. 为什么需要索引堆？

堆结构的数据增删操作，需要swap操作。虽然可以被优化成每次一次赋值，然而当元素类型是复杂数据机构（例如：类、浮点数、结构体等），赋值操作的消耗不容小觑。

因此，如果可以通过交换整数数据，来实现堆的数据操作，就会大大提高程序性能。而索引堆就是为此而生。

2. 堆和索引堆

友情链接：《堆、堆排序和优先队列的那些事》

在堆的基础上，增加一个整数数组indexes。

indexes[i]就代表：堆中第 i 个元素在所属数组中的位置。

如下图所示, index[1]代表堆中的第 1 个元素是data中的第 10 个元素。

image

因此，有了indexes数组，data数组不要变动，只需要维护indexes数组即可表示堆中的数据顺序。

3. 反向查找

当我们需要改变原来data数组中的一个数据并且维护堆的结构，需要反向索引来帮助。

堆中引入reverse数组。reverse[i]代表索引 i 在indexes数组的位置。

如下图所示, reverse[1]代表 1 在indexes中的位置是 8。

image

借助反向查找，当我们修改第 9 个元素的时候，访问reverse[9]便可以知道data[9]在堆中的位置是 2。时间复杂度降低到O(1)。

为了方便理解，请看后面实现的MaxIndexHeap.h中的void change(int i, Item new_item)函数。

4. 代码实现

4.1 实现最大堆

MaxIndexHeap.h代码如下：

//
// Created by godbmw.com on 2018/9/26.
//

#ifndef MAXHEAP_INDEXMAXHEAP_H
#define MAXHEAP_INDEXMAXHEAP_H

#include <iostream>
#include <algorithm>
#include <cassert>
#include <typeinfo>

using namespace std;

template <typename Item>
class IndexMaxHeap {
private:
    Item* data; // 堆数据存放
    int* indexes;
    int* reverse;
    int count; // 堆目前所含数据量大小
    int capacity; // 堆容量大小

    void shift_up(int k) {
        while( k > 1 && data[indexes[k/2]] < data[indexes[k]]) {
//          交换堆中2个元素的位置, 但是不操作data数组
//          相当于交换 int 型数据，比交换Item更有效
            swap(indexes[k/2], indexes[k]);
//          交换后reverse的对应值
//          更新在indexes中的位置
            reverse[indexes[k/2]] = k/2;
            reverse[indexes[k]] = k;
            k /= 2;
        }
    }

    void shift_down(int k) {
        while( 2*k <= count ) {
            int j = 2*k;
            if( j+1 <= count && data[indexes[j+1]] > data[indexes[j]]) {
                j+=1;
            }
            if(data[indexes[k]] >= data[indexes[j]]) {
                break;
            }
            swap(indexes[k], indexes[j]);
            reverse[indexes[k]] = k;
            reverse[indexes[j]] = j;
            k = j;
        }
    }
public:
    IndexMaxHeap(int capacity) {
        this->data = new Item[capacity + 1]; // 堆中数据从索引为1的位置开始存储
        this->indexes = new int[capacity + 1];
        this->reverse = new int[capacity + 1];
        for(int i = 0; i < this->capacity + 1; ++i) {
            this->reverse[i] = -1;
        }
        this->count = 0;
        this->capacity = capacity;
    }
    ~IndexMaxHeap(){
        delete[] this->data;
        delete[] this->indexes;
        delete[] this->reverse;
    }
//    返回堆中元素个数
    int size() {
        return this->count;
    }
//    返回布尔值：堆中是否为空
    bool is_empty() {
        return this->count == 0;
    }

//    向堆中插入元素Item, i是元素索引
    void insert(int i, Item item) {
        assert(this->count < this->capacity);
        assert( i >= 0 && i <= this->capacity);
//        对外部用户而言, 是从索引0开始的
        i += 1;
        this->data[i] = item;
        this->indexes[this->count + 1] = i;
        this->reverse[i] = this->count + 1;
        this->count++;
        this->shift_up(this->count);
    }

//    取出最大值
    Item extract_max() {
        assert(this->count > 0);
        Item ret = this->data[this->indexes[1]]; // 取出根节点
        swap(this->indexes[1], this->indexes[this->count]); // 将根节点元素和最后元素交换
        this->reverse[this->indexes[1]] = 1;
        this->reverse[this->indexes[this->count]] = -1;
        this->count --; // 删除最后一个元素
        this->shift_down(1); // shift_down 将元素放到应该在的位置
        return ret;
    }

    int extract_max_index() {
        assert(this->count > 0);
        int ret = this->indexes[1] - 1;
        swap(this->indexes[1], this->indexes[this->count]);
        this->reverse[this->indexes[1]] = 1;
        this->reverse[this->indexes[this->count]] = -1;
        this->count --;
        this->shift_down(1);
        return ret;
    }

    bool contain(int i) {
        assert( i >= 0 && i <= this->capacity);
        return reverse[i+1] != -1;
    }

    Item get_item(int i) {
        assert(this->contain(i));
        return this->data[i+1];
    }

    void change(int i, Item new_item) {
        assert(this->contain(i));
        i += 1;
        this->data[i] = new_item;
//        找到 indexes[j] = i, j 表示data[i]在堆中的位置
//        之后shift_up 和 shift_down
//        for(int j = 1; j <= this->count; ++j) {
//            if(this->indexes[j] == i) {
//                this->shift_up(j);
//                this->shift_down(j);
//                return;
//            }
//        }

//      利用 reverse 实现反向查找, 从 O(n) => O(1)
        int j = this->reverse[i];
        this->shift_up(j);
        this->shift_down(j);
    }
};

#endif //MAXHEAP_INDEXMAXHEAP_H

4.2 测试代码

main.cpp代码如下：

#include <iostream>
#include <ctime>
#include <algorithm>
#include "MaxHeap.h"
#include "IndexMaxHeap.h"
#include "SortHelper.h"

#define HEAP_CAPACITY 10
#define MAX_NUM 100

using namespace std;
int main() {
    IndexMaxHeap<int> index_max_heap = IndexMaxHeap<int>(HEAP_CAPACITY);
    srand(time(NULL));
    for(int i = 0; i < HEAP_CAPACITY - 2 ; i++) {
        index_max_heap.insert(i, rand() % MAX_NUM);
    }
    cout<<endl;

    index_max_heap.change(1, 109);

    while( !index_max_heap.is_empty() ) {
        cout<< index_max_heap.extract_max() << " ";
    }
    cout<<endl;
    return 0;
}