So erstellen Sie eine Hilfsdatenstruktur, um die Heap -Indizes in einem Mindeap für den Operation von Decriase_key in C ⇐ C++

[Anonymous]

Ich denke, das ist wahrscheinlich ein triviales Problem, aber ich habe seit einigen Tagen damit zu kämpfen. < /p>

Ich habe den folgenden Vektor: v = [7,3,16,4,2,1] < /code>. Ich konnte mit Hilfe von Google Simple Minheap -Algorithmus mit Hilfe implementieren, um das kleinste Element in jeder Iteration zu erhalten. Nach der Extraktion des minimalen Elements muss ich die Werte einiger Elemente verringern und sie dann aufsprudeln. < /p>

Das Problem, das ich habe, ist, dass ich die Elemente finden möchte, deren Wert im Haufen in konstanter Zeit < /strong> reduziert werden muss, dann diesen Wert reduzieren und dann aufblasen.

Nach dem Heapify -Vorgang sieht der Heap_Vector v_h so aus: v_h = [1,2,7,4,3,16] . Wenn ich das Minelement 1 entferne, wird der Heap -Vektor [2,3,7,4,16] . Aber bevor wir den Tausch durchführen und aufblasen, sagen ich, ich möchte die Werte von 7 bis 4, 16 bis 4 und 4 auf 3,5 ändern. Aber ich bin mir nicht sicher, wo sie auf dem Haufen sein werden. Die Werteindizes der Elemente, die verringert werden müssen, werden in Bezug auf den ursprünglichen Vektor V angegeben. Ich habe herausgefunden, dass ich eine Hilfsdatenstruktur haben muss, die die Haufenindizes in Bezug auf die ursprüngliche Reihenfolge der Elemente verfolgen kann (der Heap -Indexvektor sollte wie H_IV = [2,4,5,3,1,0] aussehen. Heap -Indizes, wenn es eine Änderung gibt, aber ich kann es nicht tun. Wer kann mich in eine Richtung führen, um mein Problem zu lösen.

Code: Select all

#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>

Die .cpp -Datei < /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