如何创建一个辅助数据结构来跟踪 c++ 中 decrease_key 操作的最小堆中的堆索引

Question

我认为这可能是一个需要解决的小问题，但过去几天我一直在努力解决这个问题。

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

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

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

我将我的作品粘贴到这里和 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

"I want to change the values of 7 to 4, 16 to 4 and 4 to 3.5 . But I am not sure where they will be in the heap. The indices of values of the elements that have to be decreased will be given with respect to the original vector v. ... Please also let me know if I have to rethink some of my logic."

与其操纵堆内的值，我建议将需要更改的值保留在向量内（可能是 v 本身）。堆可以基于结构（或 class）的元素，这些元素将 index 保存到具有值的向量中的相应位置，而不是保存（更改) 值本身。

该结构（或 class）将实现一个 operator< 函数，该函数比较从两个向量位置检索到的相应索引值的值。因此，不是将比较值存储在堆元素中并比较 a < b，而是存储索引位置 i 和 j 等并比较 v[i] < v[j] 以达到堆排序的目的。

这样，您需要更新的数值的位置将永远不会改变原来的位置。位置信息永远不会过时（我从你的描述中了解到）。

当然，当您更改向量中的那些存储值时，这很容易使堆本身中可能存在的任何排序无效。据我了解你的描述，无论如何，这都是必然的。因此，根据您更改值的方式，您可能需要重新执行 make_heap 以恢复正确的堆排序。（这还不清楚，因为这取决于您的预期更改是否违反堆假设，但除非有其他强有力的保证，否则假设是安全的。）

我认为剩下的就很简单了。您仍然可以像以前那样操作堆。为方便起见，您甚至可以为结构（或 class）提供一个查找函数，以 return 向量中相应位置的当前值，如果您在弹出时需要它（而不是索引）最小值。

p.s。这是同一想法的变体。

在上面的原始版本中，可能还需要存储指向保存值向量的向量位置的指针，可能作为该结构的共享静态指针（或 class）这样所有成员都可以取消引用指向该向量的指针并结合索引值来查找与该元素关联的特定成员。

如果您愿意，不是在每个成员中存储共享向量指针和索引，每个结构（或 class）实例可以更简单地将指针（或迭代器）直接存储到相应值的位置.如果值是整数，则堆元素结构的成员值可以是 int 指针。虽然每个指针都可能大于索引值，但这确实有一个优点，即它消除了对保存比较值的数据结构的任何假设，甚至 simpler/faster 取消引用与使用索引查找向量. （都是常数时间。）

一个警告：在这种替代方法中，如果您要导致向量的存储位置发生变化，则指针值将失效，例如通过推入新值并以迫使它重新分配它的方式扩展它 space。我假设您只需要更改值，而不是在开始使用堆后扩展值的数量。但是，如果您确实需要这样做，那将是更喜欢索引值的原因之一，因为它们在扩展向量后仍然有效（与指针不同）。

p.p.s。当您要在堆中比较的对象很大时，此技术也很有价值。与其让堆在对堆元素的位置重新排序时对大对象执行许多复制操作，不如通过仅存储指针（或索引值）进行复制，效率要高得多。事实上，这使得在您可能根本不想复制的对象上使用堆成为可能。

这里是比较函数的一个版本的快速概念（现在添加了一些 class 上下文）。

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.

如果您需要对不同类型的值或对象执行此操作，则可以使用一个模板来实现指针方法，该模板概括了值或对象的类型并包含指向该通用类型的指针。

如何创建一个辅助数据结构来跟踪 c++ 中 decrease_key 操作的最小堆中的堆索引

How to create an auxiliary data structure to keep track of heap indices in a minheap for the decrease_key operation in c++

c++

algorithm

heap