对上一个问题的补充

来源: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 

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


//img.mukewang.com/szimg/6097411b09151df418100918.jpg

0
4
慕移动9586716
回复
liuyubobobo
老师,那现在我就这样吧添加insert(11, 20) //索引为:11 , 真实数据为:20 ,在索引堆能容纳的情况下,我根据你的源代码在稿纸上run下来,他是添加在上图索引堆中5的右孩子的位置,但是这时候就不满足最大索引堆的定义了,他究竟该添加在哪一个位置呀?,或者是需要进一步的维护最大索引堆?
2021-05-09
共4条回复

liuyubobobo

2021-05-09

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


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

0
4
慕移动9586716
回复
liuyubobobo
//酷!
2021-05-10
共4条回复

算法与数据结构(C++版) 面试/评级的算法复习技能包

课程专为:短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

查看课程