c++ - 如何创建辅助数据结构以在minheap中跟踪堆索引以进行C++中的reduce_key操作

Question

我认为这可能是一个微不足道的问题，但过去几天我一直在为此苦苦挣扎。

我有以下 vector :v = [7,3,16,4,2,1]。我能够在Google简单的minheap算法的帮助下实现，以在每次迭代中获取最小的元素。提取最小元素后，我需要减小某些元素的值，然后将它们冒泡。

我遇到的问题是，我想在常量中以恒定的时间在堆中找到其值必须减小的元素，然后减小该值，然后将其冒泡。

在执行heapify操作之后，heap_vector v_h看起来像这样:v_h = [1,2,7,4,3,16]。当我删除min元素1时，堆 vector 变成[2,3,7,4,16]。但是在进行交换和冒泡之前，请说我想将7的值更改为4，将16的值更改为4并将将4的值更改为3.5。但是我不确定它们将在堆中的什么位置。相对于原始 vector v，将给出必须减少的元素的值的索引。我发现我需要有一个辅助数据结构，该结构可以跟踪与元素的原始顺序有关的堆索引(在将所有元素插入minheap之后，堆索引 vector 应看起来像h_iv = [2,4,5,3,1,0]。每当从minheap中删除一个元素时，heap_index应该为-1。我创建了一个 vector ，试图在有变化时尝试更新堆索引，但是我做不到。

我正在这里粘贴工作，也在https://onlinegdb.com/SJR4LqQO4
我尝试过的一些工作已被注释掉。当冒泡或冒泡操作发生交换时，我无法映射堆索引。我将非常感谢任何能引导我解决问题的人。还请让我知道是否需要重新考虑一些逻辑。

.hpp文件

#ifndef minheap_hpp
#define minheap_hpp

#include <stdio.h>
// #include "helper.h"
#include <vector>

class minheap
{
public:
    std::vector<int> vect;
    std::vector<int> heap_index;
    void bubble_down(int index);
    void bubble_up(int index);
    void Heapify();

public:
    minheap(const std::vector<int>& input_vector);
    minheap();

    void insert(int value);
    int  get_min();
    void delete_min();
    void print_heap_vector();
};


#endif /* minheap_hpp */

.cpp文件

#include "minheap.hpp"

minheap::minheap(const std::vector<int>& input_vector) : vect(input_vector)
{
    Heapify();
}

void minheap::Heapify()
{
    int length = static_cast<int>(vect.size());
//    auto start = 0;
//    for (auto i = 0; i < vect.size(); i++){
//        heap_index.push_back(start);
//        start++;
//    }
    for(int i=length/2-1; i>=0; --i)
    {
        bubble_down(i);
    }
}


void minheap::bubble_down(int index)
{
    int length = static_cast<int>(vect.size());
    int leftChildIndex = 2*index + 1;
    int rightChildIndex = 2*index + 2;

    if(leftChildIndex >= length){
        return;
    }

    int minIndex = index;

    if(vect[index] > vect[leftChildIndex])
    {
        minIndex = leftChildIndex;
    }

    if((rightChildIndex < length) && (vect[minIndex] > vect[rightChildIndex]))
    {
        minIndex = rightChildIndex;
    }

    if(minIndex != index)
    {
        std::swap(vect[index], vect[minIndex]);
//        std::cout << "swap " << index << " - " << minIndex << "\n";
//        auto a = heap_index[heap_index[index]];
//        auto b = heap_index[heap_index[minIndex]];
//        heap_index[a] = b;
//        heap_index[b] = a;
//        print_vector(heap_index);
        bubble_down(minIndex);
    }
}


void minheap::bubble_up(int index)
{
    if(index == 0)
        return;

    int par_index = (index-1)/2;

    if(vect[par_index] > vect[index])
    {
        std::swap(vect[index], vect[par_index]);
        bubble_up(par_index);
    }
}

void minheap::insert(int value)
{
    int length = static_cast<int>(vect.size());
    vect.push_back(value);
    bubble_up(length);
}

int minheap::get_min()
{
    return vect[0];
}

void minheap::delete_min()
{
    int length = static_cast<int>(vect.size());

    if(length == 0)
    {
        return;
    }
    vect[0] = vect[length-1];
    vect.pop_back();
    bubble_down(0);
}


void minheap::print_heap_vector(){
    // print_vector(vect);
}

和主文件

#include <iostream>
#include <iostream>
#include "minheap.hpp"


int main(int argc, const char * argv[]) {


    std::vector<int> vec {7, 3, 16, 4, 2, 1};

    minheap mh(vec);

    // mh.print_heap_vector();

    for(int i=0; i<3; ++i)
    {
        auto a = mh.get_min();
        mh.delete_min();
        // mh.print_heap_vector();
        std::cout << a << "\n";

    }
//    std::cout << "\n";


    return 0;
}

Answer 1

“我想将7，4，16到4以及4到3.5的值更改。但是我不确定它们在堆中的位置。必须降低的元素的值的索引将给出原始 vector v。...也请让我知道是否需要重新考虑一些逻辑。”

我建议不要将需要更改的值保留在 vector 内部(可能是v本身)，而不是在堆内部操作。堆可以基于作为结构(或类)的元素，这些元素使用值在 vector 中的相应位置保存一个索引，而不是保存(更改)值本身。

该结构(或类)将实现operator <函数，该函数比较从两个 vector 位置中检索到的值以获取相应的索引值。因此，不是将比较值存储在堆元素中并比较a
这样，您需要更新的数值的位置将不会从其原始位置改变。职位信息永远不会过时(据我从您的描述中了解)。

当然，当您对 vector 中的存储值进行更改时，这很容易使堆本身中可能存在的任何顺序无效。据我了解，您的描述在任何情况下都是正确的。因此，根据更改值的方式，可能需要执行新的make_heap以恢复正确的堆顺序。 (尚不清楚，因为这取决于您的预期更改是否违反堆假设，但是除非有其他有力保证，否则假设是安全的。)

我认为其余的内容很简单。您仍然可以按预期操作堆。为简便起见，您甚至可以给struct(或类)一个查找函数，以在 vector 中其对应位置返回当前值，如果您在弹出最小值时需要该值(而不是索引)。

ps这是同一想法的变体。

在上述原始版本中，可能还需要存储指向保存值 vector 的 vector 位置的指针，可能作为该结构(或类)的共享静态指针，以便所有成员都可以取消引用该指针。该 vector 与索引值结合使用，以查找与该元素关联的特定成员。

如果愿意，可以将每个结构(或类)实例直接存储到对应值位置的指针(或迭代器)，而不是将共享的 vector 指针和索引存储在每个成员中。如果值是整数，则堆元素结构的成员值可以是int指针。尽管每个指针都可能大于索引值，但这样做的确具有以下优点:它消除了关于保存比较值的数据结构的任何假设，并且与在 vector 中使用索引进行解引用和查找相比，它更简单/更快。 (都是固定时间。)

一个警告:在这种替代方法中，如果要使 vector 的存储位置发生变化，例如，指针值将无效。通过推入新值并以迫使其重新分配其空间的方式扩展它。我假设您只需要更改值，而不用在开始使用堆之后扩展值的数量。但是，如果确实需要这样做，那就是选择索引值的原因之一，因为索引值在扩展 vector 后仍然有效(与指针不同)。

p.p.s.当您要在堆中比较的对象很大时，此技术也很有值(value)。通过仅存储指针(或索引值)，堆就不会对大型对象执行许多复制操作，因为它只对指针(或索引值)进行重新排序，因此复制效率更高。实际上，这使您可以在根本不想复制的对象上使用堆。

这是比较函数一个版本的快速构想(现在添加了一些类上下文)。

class YourHeapElementClassName
{
public:

// constructor
explicit YourHeapElementClassName(theTypeOfYourComparableValueOrObject & val)
: m_valPointer(&val)
{
}

bool operator<(const YourHeapElementClassName & other) const
{
    return *m_valPointer < *(other.m_valPointer);
}

...

private:

theTypeOfYourComparableValueOrObject * m_valPointer;

}; // YourHeapElementClassName

// and later instead of making a heap of int or double,
// you make a heap of YourHeapElementClassName objects
// that you initialize so each points to a value in v
// by using the constructor above with each v member.
// If you (probably) don't need to change the v values
// through these heap objects, the member value could be
// a pointer to a const value and the constructor could
// have a const reference argument for the original value.

如果您需要使用不同类型的值或对象来执行此操作，则可以使用模板来实现指针方法，该模板可以对值或对象的类型进行归纳并保留指向该常规类型的指针。