3. Binary Heap - was ist falsch?

Binary Heap - was ist falsch?

  • E

    Hier ist nun im folgenden mein Code zu einem Binary Heap. Mir schien es super verständlich und ich finde das Thema toll. Aber mein Code hat einen Fehler. Nach stundenlangem draufstarren und ausprobieren, bin ich noch immer keinen Schritt weiter.

    #include "BinaryHeap.h"
BinaryHeap::BinaryHeap()
{
    elements_in_heap=0;
    array_ptr=new aircraft*[capacity];
}
BinaryHeap::~BinaryHeap()
{
    delete array_ptr;
}
bool BinaryHeap::isEmpty()
{
    if(elements_in_heap == 0) return true;
    else return false;
}
aircraft* BinaryHeap::getMin()
{
   if(elements_in_heap == 0) return NULL;
   return array_ptr[0];
}
int BinaryHeap::parent(int i)
{
    return ((i-1)/2);
}
int BinaryHeap::left(int i)
{
    return (i*2+1);
}
int BinaryHeap::right(int i)
{
    return (i*2+2);
}
void BinaryHeap::swapElements(int x, int y)
{
    aircraft* hilf= array_ptr[x];
    array_ptr[x]=array_ptr[y];
    array_ptr[y]=hilf;
}
void BinaryHeap::siftUp(int i)
{
    while(i>0 && (array_ptr[parent(i)]->priority) > (array_ptr[i]->priority)){
        swapElements(i, parent(i));
        i=(i-1)/2;
    }
}
void BinaryHeap::siftDown(int i)
{
    int m;
    while(left(i)<elements_in_heap){
        if(right(i)>=elements_in_heap) m=left(i);
        else{
            if(array_ptr[left(i)]->priority<array_ptr[right(i)]->priority) m= left(i);
            else m=right(i);
        }
        if(array_ptr[i]->priority<=array_ptr[m]->priority) return;
        else{
            swapElements(i, m);
            i=m;
        }
    }
}
void BinaryHeap::insertElement(aircraft* new_elem)
{
    if(elements_in_heap==capacity) return;
    else{
    elements_in_heap++;
    array_ptr[elements_in_heap-1]=new_elem;
    siftUp(elements_in_heap-1);
    //elements_in_heap++;
    }
}
int BinaryHeap::findElement(aircraft* elem)
{
    for(int i=0; i<elements_in_heap; i++){
        if(array_ptr[i]==elem) return i;
    }
    return -1;
}
void BinaryHeap::decreaseElement(aircraft* elem, acft_priority new_priority)
{
    if(elem->priority>new_priority) elem->priority=new_priority;
    else return;
}
aircraft* BinaryHeap::extractMin()
{
    if(elements_in_heap==0) return NULL;
    else if(elements_in_heap==1){
        elements_in_heap--;
        return array_ptr[0];
    }
    else{
    aircraft* zwischen= array_ptr[0];
    array_ptr[0]=array_ptr[elements_in_heap-1];
    elements_in_heap--;
    siftDown(0);
    return zwischen;
    }
}
void BinaryHeap::deleteElement(aircraft* elem)
{
    elem->priority=DELETE;
    siftUp(findElement(elem));
    extractMin();
    //int hilf= findElement(elem);
    //swapElements(0, hilf);
    //extractMin();
    //siftUp(elements_in_heap-1);
}
void BinaryHeap::print()
{
    if(elements_in_heap == 0)
    {
        cout << "no elements" << endl;
        return;
    }
    cout << array_ptr[0]->priority;
    for(int i=1; i<elements_in_heap; i++)
        cout << " - " << array_ptr[i]->priority ;
    cout << endl;
}
aircraft** BinaryHeap::getArray()
{
    return array_ptr;
}
int BinaryHeap::getSize()
{
    return elements_in_heap;
}

    Anscheinend besteht mein Code die folgende Testbench nicht, weil die Anzahl der enthaltenen Elemente nicht mit den Beispielen übereinstimmen.

    #include <iostream>
#include "BinaryHeap.h"
#include "aircraft.h"

using namespace std;
void print_testArrays(int test_array[], int length)
{
    cout << test_array[0];
    for(int i=1; i<length; i++)
    {
        cout << " - "  << test_array[i];
    }
    cout << endl;
}
bool compare_heap(BinaryHeap* bh, int test_array[], int length)
{
    int elements_in_heap = bh->getSize();
    aircraft** array_ptr = bh->getArray();

    if(elements_in_heap != length)
    {
        cout << "Test failed. Too few/many elements in the heap" << endl;
        return false;
    }

    for(int i=0; i<elements_in_heap; i++)
    {
        if(array_ptr[i]->priority!=test_array[i])
        {
            cout << "Test failed." << endl;
            cout << "The heap is " << endl;
            bh->print();
            cout << "but should be" << endl;
            print_testArrays(test_array, length);
            return false;
        }
    }
    return true;
}
void test(BinaryHeap* bh)
{
    int test_array1[1] = {3};
    int test_array2[2] = {2,3};
    int test_array3[3] = {2,3,2};
    int test_array4[4] = {1,2,2,3};
    int test_array5[3] = {1,3,2};
    int test_array6[3] = {1,3,1};
    int test_array7[4] = {1,3,1,4};
    int test_array8[3] = {1,3,4};

    aircraft* state3 = new aircraft(STATE);
    aircraft* amb2  = new aircraft(AMBULANCE);
    aircraft* amb2b = new aircraft(AMBULANCE);
    aircraft* emeg1 = new aircraft(EMERGENCY);
    aircraft* reg1  = new aircraft(REGULAR);

    //cout << "insert state3" << endl;
    bh->insertElement(state3);
    if(!compare_heap(bh, test_array1, 1))
        return;

    //cout << "insert amb2" << endl;
    bh->insertElement(amb2);
    if(!compare_heap(bh, test_array2, 2))
        return;

    //cout << "insert amb2b" << endl;
    bh->insertElement(amb2b);
    if(!compare_heap(bh, test_array3, 3))
        return;

    //cout << "insert emeg1" << endl;
    bh->insertElement(emeg1);
    if(!compare_heap(bh, test_array4, 4))
        return;

    //cout << "delete amb2" << endl;
    bh->deleteElement(amb2);
    if(!compare_heap(bh, test_array5, 3))
        return;

    //cout << "delete amb2" << endl ;
    bh->deleteElement(amb2);
    if(!compare_heap(bh, test_array5, 3))
        return;

    //cout << "dec amb2b to emergency" << endl;
    bh->decreaseElement(amb2b, EMERGENCY);
    if(!compare_heap(bh, test_array6, 3))
        return;

    //cout << "insert reg1" << endl;
    bh->insertElement(reg1);
    if(!compare_heap(bh, test_array7, 4))
        return;

    //cout << "extract min" << endl;
    bh->extractMin();
    if(!compare_heap(bh, test_array8, 3))
        return;

    cout << endl;
    cout<< "All tests passed!" << endl;
    cout << endl;
    cout<< "Remember to comment your code :)" << endl;
}

int main()
{
    BinaryHeap bh;
    test(&bh);
}

    Für mich kam also nur in Frage, dass es die folgenden drei Funktionen sein können, die den Fehler liefern:
    insertElement
    deleteElement
    extractMin
    , da ich nur bei diesen etwas an der Anzahl der Elemente verändere.
    Ich war so überzeugt von meinem Code und nun ziemlich verzweifelt.

    Liebe Grüße

    0
  • ?

    Warum benutzt du keinen std::vector?

    Die Klasse verletzt die 3/5/0er Regel.

    0
    E
     1 Antwort

  • 6/3/0

    0
  • E

    @manni66 Die Header sollen nicht verändert werden. Es ist möglich auch ohne weitere Header keine Fehlermeldungen mehr zu bekommen.

    0

  • Wie wäre es mit einem Minimal, Reproducible Example?

    (Nein, die meisten haben keine lust mehrere Dateien zusammenzustückeln und zu erraten, was wohl in BinaryHeap.h und aircraft.h stehen könnte.)

    0
    E
     1 Antwort
  • E

    @Swordfish dann ganz und gar banal gefragt; wenn ich nur eine Funktion habe, bei der ich Elemente hinzufüge, und ich in dieser meine Variable für die Anzahl der Elemente inkrementiere bzw und eine Funktion, mit der ich das kleinste Element lösche und dort diese Variable dekrementiere (und die andere löschen Funktion eben diese aufruft), wie kann dann die Anzahl falsch sein, wenn es nur über diese Funktionen gesteuert wird?

    0 1 Antwort

  • @easterbunny Tut mir leid, aber das ist eine ziemlich sinnfreie frage. Da gibt es also zwei Funktionen, eine fügt also Elemente irgendwo (wo?, wie?) hinzu und eine andere entfernt sie (wo?, wie?). Bring ein MCVE und dir wird gehelft werden können.1)

    1) von mir heute nichtmehr. Gute Nacht.

    0
  • W

    @easterbunny

    Es ist möglich auch ohne weitere Header keine Fehlermeldungen mehr zu bekommen.

    Es ist auch möglich, sich zum Nagel in die Wand schlagen erst einen krummen Hammer selbst zu bauen. Mannis Alternative sieht vor, einfach einen ordentlichen Hammer aus dem Werkzeugkasten zu benutzen.

    @easterbunny sagte in Binary Heap - was ist falsch?:

    Für mich kam also nur in Frage, dass es die folgenden drei Funktionen sein können, die den Fehler liefern:
    insertElement
    deleteElement
    extractMin

    Da sind doch etliche Tests drin. Die ersten Tests machen nur insert. Wenn du also zu deinen Test noch ausgibst, was sie testen, wirst du sehen, welcher Test fehlschlägt. Ich würde mal sagen, dein deleteElement ist fragwürdig. Was machst du da? Tausche die zu löschende Node mit der letzten Node und bubbele sie dann entweder hoch oder runter (je nachdem, in welcher Richtung der Parent liegt).

    Du hast außerdem Speicherlecks im Code. Statt NULL verwende nullptr (typsicher).

    0
  • S

    Bist du dir sicher, dass du ein "Array" von Pointern verwenden möchtest?

    Deine Test Suit macht doch die schöne Ausgabe "Remember to comment your code :)" (zumindest wenn die Erfolgreich durchgelaufen ist), warum sehe ich da keine Kommentare?

    0
binary heap 1
Anmelden zum Antworten