C++ sieben runter Heap

Ich schreibe ein Programm, das erfordert, dass ich einen Heap verwenden, und alles läuft gut neben meiner Sortiermethoden, offensichtlich sehr wichtig! Ich bin mir nicht sicher, was mit meiner Logik nicht stimmt oder ob mir etwas Dummes fehlt. Aber ein frischer Blick darauf wäre schön.C++ sieben runter Heap

Die Funktion wird mein Vektor übergeben, der natürlich der Heap ist, der Speicherort der Wurzel und dann entweder die STL weniger oder größer als ein Prädikat.

template<class T,class P> 
void upheap(vector<T>& v, int start, P func) { 
    T x = v[start]; 
    while (start > 1 && func(x, v[start/2])) { 
     v[start] = v[start/2]; start /= 2; 
    } 
    v[start] = x; 
}

Irgendeine Idee, was ist falsch?

Quelle

2010-12-03 rajh2504

Sie sagen, Sie übergeben die Wurzel des Heaps? Sollten Sie nicht den Index des Elements übergeben, das aufgetischt werden muss? –

Entschuldigung ja das ist was ich meine es ist der Index Wert. – rajh2504

Vielleicht solltest du die Invarianten, Vorbedingungen und Nachbedingungen schreiben und dann wirst du vielleicht den Ärger sehen. Zum Beispiel, ist die Bedingung 'HEAP (i = 0 .. start-1)' wahr bei der Eingabe? Und dann ist das Ziel, dass die Bedingung "HEAP (i = 0..start)" beim Verlassen wahr sein sollte? –

Das erste Element in einem Vektor ist v [0]. Du scheinst anzunehmen, dass es bei v [1] ist. Gibt es einen Grund dafür? Wenn die Wurzel bei v [0] liegt und ein Knoten am Index i ist, befindet sich das übergeordnete Element bei int ((i-1)/2) (obwohl (i-1) >> 1 effizienter sein könnte). und die Kinder sind bei 2i + 1, 2i + 2. Beispiel:

 0 
    1 2 
3 4 5 6 
78 9A BC DE

Auf der anderen Seite, wenn die Wurzel bei V [1] ist, ist die Mutter bei int (i/2) (oder i >> 1), und die Kinder sind bei 2i, 2i +1. Zum Beispiel:

 1 
    2 3 
4 5 6 7 
89 AB CD EF

Das könnte also ein Problem sein.

Sie überprüfen, um zu sehen, ob func (x, v [/ 2 starten]) wahr ist. Wenn func die Heap-Bedingung ist, möchten Sie vielleicht überprüfen, ob das falsch ist ...

Ist der Vektor bereits groß genug, um v [start] einzuschließen? Wenn upheap() wird verwendet, um Elemente in den Heap einzeln hinzuzufügen ... Und die Größe des Vektors wird nie erhöht ... (Sie beginnen auch bei v [1], nicht v [0]. Das ist ein zusätzliches Element.)

Haben Sie versucht, ein einfaches Gerüst (Code, der zum Testen/Debuggen verwendet wird, aber nicht Teil des Endprodukts) Routine zum Drucken des Heap, Hinzufügen in Ihre Schleife und zum Ausführen mit Daten üben, um zu sehen, wo die Dinge ausgehen?

Quelle

2010-12-03 05:32:25

C++ sieben runter Heap

Antwort

Verwandte Themen