Как создать вспомогательную структуру данных, чтобы отслеживать индексы кучи в MinHeap для работы DIDESE_KEY в C ++ ⇐ C++

[Anonymous]

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

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

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

После операции 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] после Обновите индексы кучи, когда есть изменения, но я не могу сделать это. Благодаря всем, кто может привести меня в направлении, чтобы решить мою проблему.#ifndef minheap_hpp
#define minheap_hpp

#include
// #include "helper.h"
#include

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

public:
minheap(const std::vector& input_vector);
minheap();

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

#endif /* minheap_hpp */
< /code>

файл .cpp < /p>

#include "minheap.hpp"

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

void minheap::Heapify()
{
int length = static_cast(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(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

Подробнее здесь: https://stackoverflow.com/questions/553 ... s-in-a-min