Как создать вспомогательную структуру данных для отслеживания индексов кучи в minheap для операции lower_key в c ++

Question

Я думаю, что это, вероятно, тривиальная проблема для решения, но я боролся с этим в течение последних нескольких дней.

У меня есть следующий вектор: v = [7,3,16,4,2,1]. Я смог реализовать с некоторой помощью Google простой алгоритм minheap, чтобы получить наименьший элемент в каждой итерации. После извлечения минимального элемента мне нужно уменьшить значения некоторых элементов, а затем всплыть.

Проблема, с которой я столкнулся, заключается в том, что я хочу найти элементы, значение которых должно быть уменьшено в куче в постоянное время , затем уменьшить это значение и затем всплыть.

После операции heapify heap_vector v_h выглядит следующим образом: v_h = [1,2,7,4,3,16]. Когда я удаляю элемент min 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

"Я хочу изменить значения от 7 до 4, от 16 до 4 и от 4 до 3,5. Но я не уверен, где они будут в куче. Индексы значений элементов, которые должны быть уменьшены, будутдано относительно исходного вектора v. ... Пожалуйста, дайте мне знать, если мне придется переосмыслить некоторые из моей логики. "

Вместо того, чтобы манипулировать значениями внутри кучи, я бы предложил сохранить значения, которыенужно изменить внутри вектора (возможно, сам по себе).Куча может быть основана на элементах, которые являются структурой (или классом), которая содержит index в соответствующей позиции в векторе со значениями, а не содержит само (изменяющееся) значение.

Структура (или класс) будет реализовывать функцию operator <, которая сравнивает значения, извлеченные из двух векторов, для соответствующих значений индекса.Таким образом, вместо сохранения значения сравнения в элементах кучи и сравнения a <b, вы должны хранить позиции индекса i и j и т. Д. И сравнивать v [i] <v [j] с целью упорядочения кучи. </p>

Таким образом, позиции числовых значений, которые вам нужно обновить, никогда не изменятся с их исходных позиций.Информация о местоположении никогда не устареет (как я понимаю из вашего описания).

Конечно, когда вы вносите изменения в эти сохраненные значения в векторе, это может легко аннулировать любой порядок, который мог существовать вкуча сама.Насколько я понимаю ваше описание, в любом случае это обязательно было правдой.Поэтому, в зависимости от того, как вы меняете значения, вам может потребоваться выполнить новый make_heap, чтобы восстановить правильное упорядочение кучи.(Это не ясно, поскольку это зависит от того, нарушают ли ваши предполагаемые изменения допущения в куче, но было бы безопасно предположить, если нет сильных гарантий в противном случае.)

Я думаю, все остальное довольно просто.,Вы все еще можете работать с кучей, как вы и предполагали ранее.Для простоты вы могли бы даже дать структуре (или классу) функцию поиска, которая будет возвращать текущее значение в его соответствующей позиции в векторе, если вам нужно это (а не индекс), когда вы выводите минимальные значения.

ps Вот вариант той же идеи.

В приведенной выше исходной версии, скорее всего, потребуется также сохранить указатель на местоположение вектора, в котором содержится вектор значений, возможно, в качестве общей статики.указатель этой структуры (или класса), чтобы все члены могли разыменовать указатель на этот вектор в сочетании со значениями индекса для поиска конкретного члена, связанного с этим элементом.

Если вы предпочитаете, вместо сохраненияэтот общий указатель вектора и индекс в каждом члене, каждый экземпляр структуры (или класса) может более просто хранить указатель (или итератор) непосредственно в местоположении соответствующего значения.Если значения являются целыми числами, значением члена структуры элемента кучи может быть указатель int.Хотя каждый указатель может быть больше, чем значение индекса, у него есть то преимущество, что он исключает любые предположения о структуре данных, которая содержит сравниваемые значения, и еще проще / быстрее разыскивает сопоставление с поиском по индексу в векторе.(Оба имеют постоянное время.)

Одно предупреждение: в этом альтернативном подходе значения указателя будут недействительными, если вы заставите изменения позиций хранения вектора, например, путем добавления новых значений и расширения их впуть, который заставляет его перераспределить его пространство.Я предполагаю, что вам нужно только изменить значения, а не расширять количество значений после того, как вы начали использовать кучу.Но если вам нужно было это сделать, это было бы одной из причин отдавать предпочтение значениям индекса, поскольку они остаются действительными после расширения вектора (в отличие от указателей).

p.p.s. Эта техника также полезна, когда объекты, которые вы хотите сравнить в куче, большие. Вместо того, чтобы куча выполняла много операций копирования на больших объектах, поскольку она переупорядочивает позиции элементов кучи, сохраняя только указатели (или значения индекса), копирование намного эффективнее. Фактически это позволяет использовать кучу объектов, которые вы вообще не хотите копировать.

Вот краткое представление об одной версии функции сравнения (теперь добавлен некоторый контекст класса).

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.

Если вам нужно было сделать это с различными типами значений или объектов, подход указателя может быть реализован с помощью шаблона, который обобщает тип значения или объекта и содержит указатель на этот общий тип.