数据结构之索引堆(IndexHeap)

一.概念及其介绍

索引堆是对堆这种数据结构的优化，是利用真正元素的索引值来组成一个堆，可以映射出一个最大堆或者最小堆，索引堆可分为最大索引堆(IndexMaxHeap)和最小索引堆(IndexMinHeap)

为什么要索引堆：

当我们在使用堆这个数据结构的时候，需要对堆进行一系列的操作，如插入，取出等操作，我们会不断的改变相应数据的位置，此时当数据较大的时候，如每个堆中的数据都是一个较大文本等，在交换位置是就会对计算机有较大消耗；所以这里我们引入索引堆，索引堆是根据比较真正数据，但改变位置的是对应数据索引的位置真正操作的是对应数据的索引，真正数据位置不变，其优点总结如下：

• 优化了交换元素的消耗。
• 加入的数据位置固定，方便寻找。

二.结构图示(全文以最大索引堆为例)

数组对应元素

构成堆后，如下图：

三.代码实现

我们需要对之前堆的代码实现进行改造，换成直接操作索引的思维。首先构造函数添加索引数组属性 indexes。

//将数据类型设为模板类
template<typename Item>
class IndexMaxHeap 
{

//对内容进行私有化，不能让用户修改
private://data为堆中的元素
  Item *data;//开辟新的空间，用来存储新的索引  
  int *indexes;//count为元素对应的索引  
  int count;//capacity表示堆的容量  
  int capacity;

相应构造函数调整为，添加初始化索引数组。

 //构造函数，构造一个空堆，能容纳capacity个元素
IndexMaxHeap(int capacity) {
  data = new Item(capacity + 1);
  indexes = new int[capacity+1];
  count = 0;this->capacity = capacity;}
//析构函数
//进行空间的释放~IndexMaxHeap() {delete[] data;delete[] indexes;

下面我们需要定义成员函数：

//返回堆中元素个数  
    int size() {return count;}//返回一个布尔值，表示堆是否为空  
    bool isEmpty() {return count == 0;

我们要对最大索引堆进行插入操作，这里我们定义一个insert()函数

//传入的对用户而言，是从0索引开始的
void insert(int i, Item item) {
    //对capacity和进行范围限定assert(count + 1 <= capacity);assert(i+1>1 && i+1 <= capacity);//这里的索引为1开始的
  i+=1;
  data[i] = item;
//调整插入操作，indexes 数组中添加的元素是真实 data 数组的索引 indexes[count+1] = i。
  indexes[count+1] = i;
  count++;shiftUp(count);
}

和堆一样，我们需要将新插入的元素和原来堆中元素进行比较，我们交换的只是对应元素的索引，所以我们只需将原来的

data[k / 2] < data[k])

改为

data[indexes[k / 2]] < data[indexes[k]])

再将原来的

swap(data[k / 2], data[k]);

改为

swap(indexes[k / 2], indexes[k]);

下面是完整是shiftUp():

void shiftUp(int k) {  
  //此时的是用来描述索引数组的位置
  while (k > 1 && data[indexes[k / 2]] < data[indexes[k]]){
    swap(indexes[k / 2], indexes[k]);
    k /= 2;
  }
}

我们要对最大索引堆中元素进行取出，其逻辑和堆一样,我们也需要将data[1]改为 data[indexes[1]];（ 与shiftUp()同理 ）

void extractMax(){
  assert(count > 0);
  Item ret = data[indexes[1]];swap(indexes[1], indexes[count]);
  count--;shiftDown(1);return ret;
}

下面来实现shiftDown()，其数组索引方法和shiftUp()同理

void shiftDown(int k) {while (k * 2 <= count) {
   int j = k * 2;if (j + 1 <= count && data[indexes[j + 1]] > data[indexes[j]])
   j++;

   if (data[indexes[k]] >= data[indexes[j]])
     break;
      swap(indexes[k], indexes[j]);
     k = j;
   }
}

在索引堆中还有一个重要的功能，就是我们需要更新索引堆里的元素，传入需要改变值对应的索引i，和修改元素值newItem，其代码如下：

void change(int i, Item newItem)
{
  i+=1;
  data[i] = newItem;
  //找到indexes[j] = 1,j表示data[i]在堆中的位置 
  //之后shiftUp(j), shiftDown(j)  
  for(int j = 1; j <= count; j++)
    if(indexes[j] == i) {shiftUp(j);shiftDown(j);}
  return;
}

完整代码如下：

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cassert>

using namespace std;

template<typename Item>
class IndexMaxHeap {

//对内容进行私有化，不能让用户修改
private://data为堆中的元素
  Item *data;//开辟新的空间，用来存储新的索引  
  int *indexes;//count为元素对应的索引  
  int count;//capacity表示堆的容量  
  int capacity;

  void shiftUp(int k) {  //此时的是用来描述索引数组的位置
    while (k > 1 && data[indexes[k / 2]] < data[indexes[k]]){
       swap(indexes[k / 2], indexes[k]);
      k /= 2;
    } 
  }

  void shiftDown(int k) {
    while (k * 2 <= count) {
       int j = k * 2;
       if (j + 1 <= count && data[indexes[j + 1]] > data[indexes[j]])
          j++;

       if (data[indexes[k]] >= data[indexes[j]])
         break;
       swap(indexes[k], indexes[j]);
       k = j;
    }
  }

public:
    //构造函数，构造一个空堆，能容纳capacity个元素
  IndexMaxHeap(int capacity) {
    data = new Item(capacity + 1);
    indexes = new int[capacity+1];
    count = 0;this->capacity = capacity;
  }//进行空间的释放~IndexMaxHeap() {delete[] data;delete[] indexes;}

    //返回堆中元素个数  
  int size() {return count;}

    //返回一个布尔值，表示堆是否为空  
  bool isEmpty() {return count == 0;}//传入的对用户而言，是从0索引开始的
  void insert(int i, Item item) {

    //对capacity和进行范围限定
    assert(count + 1 <= capacity);
    assert(i+1>1 && i+1 <= capacity);
    //这里的索引为1开始的
    i+=1;
    data[i] = item;
    indexes[count+1] = i;
    count++;shiftUp(count);
  }

  void extractMax(){
    assert(count > 0);
    Item ret = data[indexes[1]];swap(indexes[1], indexes[count]);
    count--;shiftDown(1);return ret;
  }
  int extractMaxIndex() {
    assert(count > 0);

    int ret = indexes[1] - 1;
    swap(indexes[1], indexes[count]);
    count--;shiftDown(1);return ret;
  }

  Item getItem(int i){return data[i+1];}

  void change(int i, Item newItem){
    i+=1;
    data[i] = newItem;
    //找到indexes[j] = 1,j表示data[i]在堆中的位置
    //之后shiftUp(j), shiftDown(j)  
    for(int j = 1; j <= count; j++)
      if(indexes[j] == i) {
        shiftUp(j);
        shiftDown(j);
      }
      return;
    }
  }
};