Std :: Vektor außerhalb des Bereichs für Min-Heap: C++

Question

Ich habe eine Zeitlang an diesem Code (oder anderen Codeprojekten) gearbeitet, obwohl ich weiß, was im Grunde mit dem Code nicht stimmt, Ich habe es schwer gefunden, genau herauszufinden, wo der Vektor außerhalb der Reichweite ist. Ich habe den ganzen Morgen gdb darauf gespielt, ohne Erfolg. Ich versuche einen Min-Heap aus einem Vektor "theData" in C++ zu machen.

#include <iostream> 
#include <vector> 
#include <algorithm> 

using std::vector; 
using std::cin; 
using std::cout; 
using std::swap; 
using std::pair; 
using std::make_pair; 

class HeapBuilder { 
    private: 
     vector<int> data_; 
     vector< pair<int, int> > swaps_; 

void WriteResponse() const { 
     cout << swaps_.size() << "\n"; 
for (int i = 0; i < swaps_.size(); ++i) { 
    cout << swaps_[i].first << " " << swaps_[i].second << "\n"; 
     } 
} 

void ReadData() { 
     int n; 
     cin >> n; 
     data_.resize(n); 
     for(int i = 0; i < n; ++i) 
     cin >> data_[i]; 
} 

    void makeMinHeap(vector<int> &theData, int i, int n) { 
    int minIndex; 
    int left = 2*i; 
    int right = 2*i + 1; 
     if (left < n && theData.at(left) < theData.at(i)) { 
     minIndex = left; 
    } 
    else if (right < n && theData.at(right) < theData.at(i)) { 
     minIndex = right; 
    } 

if (minIndex != i) { 
    swap(theData.at(i), theData.at(minIndex)); 
    swaps_.push_back(make_pair(i, minIndex)); 
    makeMinHeap(theData, minIndex, n); 
    } 
} 

    void GenerateSwaps() { 
    swaps_.clear(); 
    int size = data_.size(); 
    for (int i = (size/2); i >= 0; i--) { 
    makeMinHeap(data_, i, size); 
    } 

    } 

public: 
    void Solve() { 
    ReadData(); 
    GenerateSwaps(); 
    WriteResponse(); 
    } 
}; 

int main() { 
    std::ios_base::sync_with_stdio(false); 
    HeapBuilder heap_builder; 
    heap_builder.Solve(); 
    return 0; 
} 

Answer 1

Sie überprüfen keinen minIndex. Schauen Sie, was passiert, wenn die linke Seite < = n und rechts < = n beide nicht, höchstwahrscheinlich, wenn die ganze Rekursion ist etwa zu stoppen, da Sie nur

überprüfen

minIndex != i 
// ^-- default each time is garbage which in case last>n && right>n leaves it garbage 
// hence when it comes to 
if(minIndex!=i){ 
// It's actually true where it was suppose to break out n thus throws out_of_range 
} 

Schnell n einfache Lösung wäre, eine flagcheck hinzufügen

bool flagcheck = false; 
if(){ flagcheck = true; } 
else if(){ flagcheck = true; } 
if(minIndex!=i && flagcheck){}