Heap-Einfügung ist unsortiert

Question

Ich habe eine Liste von Entitäten, die ich in C rendern möchte, und mein Render-Puffer verwendet einen Heap-Insert für jeden Frame, um sicherzustellen, dass die Entity-Tiefen in der Reihenfolge rendern. Aus irgendeinem Grund endet der Heap jedoch immer unsortiert. Ich habe Dutzende Male über den Code geschaut, hatte Freunde über den Code schauen, und ich kann einfach nicht finden warum die Entitäten sind immer außer Betrieb. Ich hoffe, dass vielleicht ein frisches Paar Augen mir helfen kann, den Fehler in meinen Wegen zu sehen. Hier ist mein kommentierten Code:

(Bitte beachten Sie, dass x, y, z, und die Tiefe (ungenutzt hier) sind alle gespeichert, wie int Einrichtungen in der Einheit structs

void AEC_RenderCatalogToBuffer(AEC_EntityCatalog* entityCatalog, 
           AEC_SpriteBuffer* spriteBuffer) 
{ 
    //The values we'll be using 
    unsigned int heap_size = 0; 
    unsigned int heap_at = 1; 
    int frame = spriteBuffer->frame + 1; 
    int x, y, z; 
    int temp_depth; 

    //Loop through all the entities 
    for (int search = 0; search < AEC_ENTITY_COUNT; search++) 
    { 
     // If an entity is drawable and it has an x, y, z, 
     // insert it into the buffer for rendering 
     if ( entityCatalog 
       ->entity_components[search].component_mask[AEC_DRAWABLE] 
      && entityCatalog 
       ->entity_components[search].component_mask[AEC_DISPLACEMENT]) 
     { 
      //Prepare data for heap insertion 
      temp_depth = AEC_GetIsoDepth(entityCatalog, search); 
      x = entityCatalog->displacement[search].x; 
      y = entityCatalog->displacement[search].y; 
      z = entityCatalog->displacement[search].z; 

      //Increase the heap size by 1, save the size as the end node 
      heap_size++; 
      heap_at = heap_size; 
      spriteBuffer->is_filled[heap_at] = frame; 

      // If the parent node is greater than 0, 
      // has a larger or equal y (depth) 
      // and is being drawn in the current frame 
      while ( (heap_at - 1)/2 > 0 
        && spriteBuffer->y[(heap_at - 1)/2] >= y 
        && spriteBuffer->is_filled[(heap_at - 1)/2] == frame 
       ) 
      { 
       spriteBuffer->entity[heap_at] 
       = spriteBuffer->entity[(heap_at - 1)/2]; 
       spriteBuffer->depth[heap_at] 
       = spriteBuffer->depth[(heap_at - 1)/2]; 
       spriteBuffer->x[heap_at] = spriteBuffer->x[(heap_at - 1)/2]; 
       spriteBuffer->y[heap_at] = spriteBuffer->y[(heap_at - 1)/2]; 
       spriteBuffer->z[heap_at] = spriteBuffer->z[(heap_at - 1)/2]; 

       heap_at = (heap_at - 1)/2; 
      } 

      // Place the new entity's information into 
      // the correct place in the array 
      spriteBuffer->is_filled[heap_at] = frame; 
      spriteBuffer->x[heap_at] = x; 
      spriteBuffer->y[heap_at] = y; 
      spriteBuffer->z[heap_at]= z; 
      spriteBuffer->entity[heap_at] = search; 
      spriteBuffer->depth[heap_at] = temp_depth; 
     } 
    } 

    // Once all the entities have submitted their draw depth 
    // and have been sorted by y-index, 
    // save the heap size and the current frame 
    spriteBuffer->size = heap_size; 
    spriteBuffer->frame = frame; 

    printf("Checking: "); 
    for (int q=0;q<heap_size+1;q++) 
    { 
     if (spriteBuffer->is_filled[q] == frame) 
     { 
      printf("%d ", spriteBuffer->y[q]); 
     } 
    } 
    printf("\n"); 
} 

Wie kann ich den Haufen Einsatz beheben. ??? Dank!

Answer 1

die binary-min-heap Sie implementiert haben sichergestellt, dass die Eltern von zwei Kindern ist kleiner als die beiden Kinder (wie @chtz hat kommentiert). Aber es garantiert nicht, dass das linke Kind kleiner ist als die richtige

Für die Prüfung ple, Ihr Haufen könnte wie folgt aussehen (Index: Wert):

0:3 
1:5  2:13 

Druck in Index-Reihenfolge Sie 3,5,13 geben würde. Dies wird zufällig sortiert. Aber die Halde könnte auch so aussehen und immer noch richtig sein:

 0:3 
1:15  2:13 

Was Sie vielleicht gedacht haben, zu tun, einen binären Suchbaum zu implementieren war.
In einem solchen Baum (eindeutige Werte annimmt)

• das linke Kind kleiner ist als die Mutter
• das richtige Kind größer ist als die Mutter

Zum Beispiel beim Einfügen (5, 1,2,3,20,10,24,12) würden Sie einen Baum wie diese:

  5 
    1   20 
_ 2  10  24 
_ _ _ 3 _ 12 _ _ 

Beachten Sie, dass ein solcher Baum nicht kompakt in einem Array ist, hat es oft leer pl Asse "_".
Wenn Sie einen solchen Baum tun möchten, müssen Sie den richtigen Ort zu finden, ein neues Mitglied, mit den Regeln hinzuzufügen. Swapping nach oben, wie in einem Heap ist nicht erforderlich.
Um einen Binärbaum zu drucken, muss er jedoch durchlaufen werden. Drucken Sie rekursiv zuerst das linke Kind, dann das Elternteil und dann das rechte Kind.
wir den Beispielsbaum Verfahrgeschwindigkeit würde:
_, _, _, 1, _, 2, 3, 5, _, 10, 12, _, 24, _
Offensichtlich ist es notwendig, um zu verfolgen, welcher Knoten tatsächlich oder leer („_“) verwendet wird; im Gegensatz zu einem Haufen.

Wenn eine Baumstruktur von geeigneter Größe wählen, sollten Sie den schlimmsten Fall, die sortierten Daten einfügt. wenn Sie
zum Beispiel 1 einzufügen, 2, 3, 5, 10, erhalten Sie:

   1 
     _    2 
    _  _  _  3 
_ _ _ _ _ _ _ 5 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 10 

Also für den Umgang mit N Werten, die Sie benötigen (2<<N)-1 Orte im Baum sicher zu sein.
oder ein Baum von dynamisch zugewiesenen Speicher mit Zeigern gebaut verwenden.
Wenn Sie den schlimmsten Fall hassen (viele Leute), dann schauen Sie sich selbst ausgleichende Bäume an.
Zum Beispiel Wikipedia.