数据结构之索引堆(IndexHeap)

数据结构之索引堆(IndexHeap)

一.概念及其介绍

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

为什么要索引堆:

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

  • 优化了交换元素的消耗。

  • 加入的数据位置固定,方便寻找。

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

数组对应元素
LK
构成堆后,如下图:

LK

三.代码实现

我们需要对之前堆的代码实现进行改造,换成直接操作索引的思维。首先构造函数添加索引数组属性 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;
  }
};
本作品采用《CC 协议》,转载必须注明作者和本文链接
刻意学习
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
118
粉丝
88
喜欢
173
收藏
245
排名:367
访问:2.6 万
私信
所有博文
社区赞助商