Binärheap erstellen



  • Hallo,

    ich bin gerade dabei, den Dijkstra-Algorithmus mit einem Binärheap als priority-queue zu erstellen und scheitere dabei, den Binärheap anfangs zu erstellen. Ich poste erstmal den Code:

    #include <stdio.h>
    #include <malloc.h>
    #include "heap_akt.h"
    
    int main(){
    
    	unsigned i;
    	KNOTEN *v;
    	HEAP *h;
    	unsigned n,m;
    
    	v=graph_read("instance01a.graph", &n, &m);
    	if(v==NULL){
    		printf("Kein Speicher\n");
    		return 0;
    	}
    
    	h=build_heap(v,n);
    
    	for (i=0; i<10; i++){
    		printf("%u\n", h->node[i]->distance);
    	}
    
    	scanf("%u", &n);
    
    	return 0;
    }
    
    #include <stdio.h>
    #include <malloc.h>
    #include "heap_akt.h"
    
    HEAP* build_heap (KNOTEN *v, unsigned n){
    
    	unsigned i;
    	HEAP *h;
    
    	h= malloc(sizeof(HEAP));
    	h->size=-1;
    	h->node=malloc(n*sizeof(KNOTEN*));
    	for (i=0; i<n; i++){
    		insert(h,v+i);
    	}
    
    	return h;
    }
    
    void insert(HEAP *h, KNOTEN *new){
    
    	unsigned i;
    
    	h->size++;
    	i= h->size;
    
    		while ((i>0) && (h->node[i/2]->distance > new->distance)){
    			h->node[i]= h->node[i/2];
    			h->node[i]->heap_pos= i;
    			i= i/2;
    		}
    
    	h->node[i]= new;
    	h->node[i]->heap_pos= i;
    
    	return;
    }
    

    Dabei ist v als Graph eingelesen, v[0].distance=5 und ansonsten v[i].distance=INFINITY, wobei .distance der Schlüssel ist, nach dem der Heap aufgebaut werden soll (oben kleinstes Element). Das mit printf in der main ist zur Kontrolle und genau da verstehe ich etwas nicht: Ich bekomme als Ausgabe folgendes:

    0
    5
    429... (MAXINT)
    429...
    429...
    usw.

    Allerdings habe ich ja niemals irgendeinen Knoten mit distance 0 initialisiert. Habe auch die Pointeradressen verglichen und ich habe nach dem ersten Eintrag (fast) den Heap, den ich haben möchte, aber ich kann mir einfach nicht erklären, wo auf einmal dieser erste Knoten herkommt. Irgendwie wurde da ein neuer Knoten hergezaubert und komplett in allen Einträgen mit 0 initialisiert.

    Compiler ist GCC unter WinXP, IDE Eclipse (falls das was ausmacht).
    Wäre super, wenn jemand von euch Rat wüsste.

    Vielen Dank und freundliche Grüße,
    plizzz



  • Hi jonny

    Probier es mit Pilzen 🙂
    Ansonsten könntest du es mal debugen !

    greetz



  • Ich habe keine Ahnung, was du meinst.



  • Also, ich weiß, was er mit debuggen meint. Dies ist auch die Lösung deines Problems. Du kannst beim Debuggen die Variablen überwachen, Zeile für Zeile durchsteppen und gucki machen, wann die 0 plumpsi macht in die Variable.
    Mit Pilzen wirst du weniger glück haben, aber die sollen ja auch ganz gut schmecken, ne.
    MfG,
    B.B.


Log in to reply