L'insertion de tas n'est pas triée

Question

J'ai une liste d'entités que je veux rendre en C, et mon tampon de rendu utilise heap insère chaque image pour m'assurer que les profondeurs des entités sont rendues dans l'ordre. Cependant, pour une raison quelconque, le tas finit toujours non trié. J'ai regardé le code des douzaines de fois, ai eu des amis regardent le code, et je ne peux pas sembler trouver pourquoi les entités sont toujours dans le désordre. J'espère que peut-être une nouvelle paire d'yeux peut m'aider à voir l'erreur dans mes moyens. Voici mon code commenté:

(S'il vous plaît noter que x, y, z, et la profondeur (non utilisée ici) sont tous stockés comme int s dans la struct entité

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"); 
} 

Comment puis-je fixer l'insert en tas. ??? Merci!

Answer 1

Le tas binaire-min que vous avez implémenté garantit seulement que le parent de deux enfants est plus petit que les deux enfants (comme @chtz l'a commenté) .Mais il ne garantit pas que l'enfant gauche est plus petit

Pour examen ple, votre tas pourrait ressembler à ceci (indice: valeur):

0:3 
1:5  2:13 

impression pour l'index vous donnera 3,5,13. Cela arrive à être trié. Mais le tas pourrait aussi regarder comme ça et être toujours correcte:

 0:3 
1:15  2:13 

Qu'est-ce que vous pourriez avoir l'intention de faire, était de mettre en œuvre un arbre de recherche binaire.
Dans un tel arbre (en supposant des valeurs uniques)

• l'enfant gauche est plus petit que le parent
• l'enfant droit est plus grand que le parent

Par exemple, lors de l'insertion (5, 1,2,3,20,10,24,12) vous obtiendrez un arbre comme celui-ci:

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

Notez qu'un tel arbre n'est pas compact dans un tableau, il a souvent pl vide aces "_".
Si vous voulez faire un tel arbre, vous devez trouver le bon endroit pour ajouter un nouveau membre, en utilisant les règles. Échange vers le haut, comme dans un tas n'est pas nécessaire.
Mais pour imprimer un arbre binaire, il faut le traverser. Imprimer récursivement, d'abord l'enfant gauche, puis le parent, puis le bon enfant.
traversée de l'arbre d'exemple donnerait:
_, _, _, 1, _, 2, 3, 5, _, 10, 12, _, 24, _
De toute évidence, il est nécessaire de garder une trace quel nœud est réellement utilisé ou vide ("_"); contrairement à un tas. Lorsque vous choisissez une structure arborescente de taille appropriée, considérez le cas le plus défavorable, qui consiste à insérer des données triées.

Par exemple, si vous insérez 1, 2, 3, 5, 10, vous obtenez:

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

Donc, pour gérer des valeurs de N vous avez besoin (2<<N)-1 place dans l'arbre pour être sûr.
Ou utilisez un arbre construit à partir de la mémoire allouée dynamiquement avec des pointeurs.
Si vous détestez le pire des cas (beaucoup de gens l'ont fait), jetez un coup d'œil à l'auto-équilibrage des arbres.
E.g. Wikipedia.