文章圖片存儲(chǔ)在GitHub，網(wǎng)速不佳的朋友，請(qǐng)看《進(jìn)擊的堆：最大索引堆》 或者 來(lái)我的技術(shù)小站 godbmw.com

1. 為什么需要索引堆？

堆結(jié)構(gòu)的數(shù)據(jù)增刪操作，需要swap操作。雖然可以被優(yōu)化成每次一次賦值，然而當(dāng)元素類型是復(fù)雜數(shù)據(jù)機(jī)構(gòu)（例如：類、浮點(diǎn)數(shù)、結(jié)構(gòu)體等），賦值操作的消耗不容小覷。

因此，如果可以通過(guò)交換整數(shù)數(shù)據(jù)，來(lái)實(shí)現(xiàn)堆的數(shù)據(jù)操作，就會(huì)大大提高程序性能。而索引堆就是為此而生。

2. 堆和索引堆

友情鏈接：《堆、堆排序和優(yōu)先隊(duì)列的那些事》

在堆的基礎(chǔ)上，增加一個(gè)整數(shù)數(shù)組indexes。

indexes[i]就代表：堆中第 i 個(gè)元素在所屬數(shù)組中的位置。

如下圖所示, index[1]代表堆中的第 1 個(gè)元素是data中的第 10 個(gè)元素。

image

因此，有了indexes數(shù)組，data數(shù)組不要變動(dòng)，只需要維護(hù)indexes數(shù)組即可表示堆中的數(shù)據(jù)順序。

3. 反向查找

當(dāng)我們需要改變?cè)瓉?lái)data數(shù)組中的一個(gè)數(shù)據(jù)并且維護(hù)堆的結(jié)構(gòu)，需要反向索引來(lái)幫助。

堆中引入reverse數(shù)組。reverse[i]代表索引 i 在indexes數(shù)組的位置。

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

image

借助反向查找，當(dāng)我們修改第 9 個(gè)元素的時(shí)候，訪問(wèn)reverse[9]便可以知道data[9]在堆中的位置是 2。時(shí)間復(fù)雜度降低到O(1)。

為了方便理解，請(qǐng)看后面實(shí)現(xiàn)的MaxIndexHeap.h中的void change(int i, Item new_item)函數(shù)。

4. 代碼實(shí)現(xiàn)

4.1 實(shí)現(xiàn)最大堆

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; // 堆數(shù)據(jù)存放
    int* indexes;
    int* reverse;
    int count; // 堆目前所含數(shù)據(jù)量大小
    int capacity; // 堆容量大小

    void shift_up(int k) {
        while( k > 1 && data[indexes[k/2]] < data[indexes[k]]) {
//          交換堆中2個(gè)元素的位置, 但是不操作data數(shù)組
//          相當(dāng)于交換 int 型數(shù)據(jù)，比交換Item更有效
            swap(indexes[k/2], indexes[k]);
//          交換后reverse的對(duì)應(yīng)值
//          更新在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]; // 堆中數(shù)據(jù)從索引為1的位置開始存儲(chǔ)
        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;
    }
//    返回堆中元素個(gè)數(shù)
    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);
//        對(duì)外部用戶而言, 是從索引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]]; // 取出根節(jié)點(diǎn)
        swap(this->indexes[1], this->indexes[this->count]); // 將根節(jié)點(diǎn)元素和最后元素交換
        this->reverse[this->indexes[1]] = 1;
        this->reverse[this->indexes[this->count]] = -1;
        this->count --; // 刪除最后一個(gè)元素
        this->shift_down(1); // shift_down 將元素放到應(yīng)該在的位置
        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 實(shí)現(xiàn)反向查找, 從 O(n) => O(1)
        int j = this->reverse[i];
        this->shift_up(j);
        this->shift_down(j);
    }
};

#endif //MAXHEAP_INDEXMAXHEAP_H

4.2 測(cè)試代碼

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