堆插入未排序

Question

我有我想要在C中呈現的實體列表，並且我的呈現緩衝區使用堆插入每個幀以確保實體深度按順序呈現。但是，由於某種原因，堆總是結束未排序。我已經瀏覽了幾十次代碼，讓朋友們看看代碼，而我似乎無法找到爲什麼實體總是出現故障。我希望或許一雙新鮮的眼睛能夠幫助我以我的方式看到錯誤。這裏是我的註釋代碼：

（請注意，X，Y，Z和深度（未用在這裏）我該如何解決堆插入都存儲爲int S IN的實體結構

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

。 ???謝謝！

Answer 1

你已經實現的二進制最小堆只保證兩個孩子的父母比兩個孩子都小（@chtz已經評論過）但它並不能保證左邊的孩子更小

對於考試您的堆可能看起來像這樣（索引：值）：

0:3 
1:5  2:13 

按索引順序打印會給你3,5,13。這恰好是排序的。 但堆也可以是這樣的，仍然是正確的：

 0:3 
1:15  2:13 

什麼你可能打算這樣做，是爲了實現一個二叉搜索樹。
在這樣的樹（假設唯一值）

• 左子是比母體
• 右子是比母體

例如大小，在插入（5時， 1,2,3,20,10,24,12），你會得到一個樹是這樣的：

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

注意，這種樹是不是在一個陣列緊湊，它有往往是空的PL王牌「_」。
如果你想做這樣的樹，你需要找到正確的地方來添加一個新成員，使用規則。向上交換，因爲不需要堆。
但是爲了打印二叉樹，它必須被遍歷。以遞歸方式打印，先是左邊的孩子，然後是父母，然後是正確的孩子。遍歷示例樹會給出：
_，_，_，1，_，2，3，5，_，10，12，_，24，_
顯然，有必要跟蹤哪個節點實際使用或爲空（「_」）;與堆相反。

當選擇適當大小的樹結構時，請考慮插入排序數據的最壞情況。
例如，如果您將1，2，3，5，10，您可以：

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

所以處理的N值，你需要在樹(2<<N)-1地方是安全的。
或者使用通過指針動態分配內存構建的樹。
如果你討厭最壞的情況（很多人都這樣做），那麼看看自平衡樹。
例如Wikipedia。