对上一个问题的补充

Question

老师，我是根据你的代码：
我调用里面的成员函数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;
    }

Answer 1

提问者 慕移动9586716 2021-05-09 10:02:46

换句话说吧，我的意思是如果我要向老师PPT（下图）中索引堆中继续添加数据，例如我添加一个public void insert(10, 20)   //索引为：10 ， 真实数据为：20 

那么按照你索引堆源代码，此时我添加的这个数据在满足索引堆的定义的条件下应该放哪里呀？

• liuyubobobo #1

  所以你的意思是添加两个索引为 10 的元素？（因为这张图中已经有一个索引为 10 的元素了）这个操作在索引堆中是不支持的。我们只能修改同一个索引的信息，不能添加两个相同的索引。所以我们的代码中有 85 行的 assert：https://git.imooc.com/coding-71/coding-71/src/master/04-Heap/Course%20Code%20%28C++%29/09-Index-Heap-Advance/main.cpp 可以参考这个问答，包括相应的链接：https://coding.imooc.com/learn/questiondetail/AKpB2PJAg0y6bv0E.html

• 提问者 慕移动9586716 回复 liuyubobobo #2

  你的代码中不是有  i += 1; 这个操作吗，此时
   i = 11  ，这个应该不重复

• liuyubobobo 回复 提问者 慕移动9586716 #3

  再添加第一个索引为 10 的时候，也会 i += 1 呀。不要应该，实际测试一下？

点开查看后面1条评论

Answer 2

liuyubobobo 2021-05-09 06:34:41

你给我的代码没有 main 函数呀。

具体对于什么测试用例，你有问题？这个问题使用课程中的代码也存在吗？你认为输出应该是怎样的？或者是算法中的某一步，哪个变量的结果应该是怎样的？但是实际是怎样的？

• 提问者 慕移动9586716 #1

  哈哈，明白了，对于索引堆，我们并没有定义它索引组成的堆是一个什么样子，所以真正的最大索引堆或者最小索引堆，其实是指真正元素最后所组成堆是一个最大堆或者最小堆，其目的就是降低直接对交换元素对计算机CPU带来的消耗

• 提问者 慕移动9586716 #2

  可以返回到prim算法的学习了

• liuyubobobo 回复 提问者 慕移动9586716 #3

  对！data 数组不是堆；indexes 数组也不是堆；是 data[indexes[i]] 为元素组成堆。这样做不是因为性能原因，而是因为堆本身除了能够拿到堆首元素，不提供访问其他元素的能力；所以我们不能更新已经放入堆中的元素。但是索引堆有这个能力。

点开查看后面1条评论