对上一个问题的补充
来源:4-8 索引堆(Index Heap)
慕移动9586716
2021-05-08
老师,我是根据你的代码:
我调用里面的成员函数insert()进行数据的添加(向空索引堆里添加数据),我在草稿上一步一步的跑了一遍,其结果就出现本小节中的上一个问题的情况了!
#include <iostream>
#include <cassert>
#include "SortTestHelper.h"
using namespace std;
// 最大索引堆
template<typename Item>
class IndexMaxHeap{
private:
Item *data; // 最大索引堆中的数据
int *indexes; // 最大索引堆中的索引
int count;
int capacity;
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
void shiftUp( int k ){
while( k > 1 && data[indexes[k/2]] < data[indexes[k]] ){
swap( indexes[k/2] , indexes[k] );
k /= 2;
}
}
// 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
void shiftDown( 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] );
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;
}
// 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
// 传入的i对用户而言,是从0索引的
void insert(int i, Item item){
assert( count + 1 <= capacity );
assert( i + 1 >= 1 && i + 1 <= capacity );
i += 1;
data[i] = item;
indexes[count+1] = i;
count++;
shiftUp(count);
}
// 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
Item 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;
}
写回答
2回答
-
慕移动9586716
提问者
2021-05-09
换句话说吧,我的意思是如果我要向老师PPT(下图)中索引堆中继续添加数据,例如我添加一个public void insert(10, 20) //索引为:10 , 真实数据为:20
那么按照你索引堆源代码,此时我添加的这个数据在满足索引堆的定义的条件下应该放哪里呀?
042021-05-09 -
liuyubobobo
2021-05-09
你给我的代码没有 main 函数呀。
具体对于什么测试用例,你有问题?这个问题使用课程中的代码也存在吗?你认为输出应该是怎样的?或者是算法中的某一步,哪个变量的结果应该是怎样的?但是实际是怎样的?
042021-05-10
相似问题