堆插入未排序

Question

我有一个要在 C 中渲染的实体列表，我的渲染缓冲区使用堆插入每个帧来确保实体深度按顺序渲染。然而，出于某种原因，堆总是以未排序的方式结束。我已经查看代码数十次，让朋友查看代码，但我似乎无法找到为什么 实体总是乱序。我希望也许有一双新的眼睛可以帮助我看到我的方式中的错误。这是我的注释代码：

（请注意，x、y、z 和深度（此处未使用）在实体结构中均存储为 ints。

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

您实施的 binary-min-heap 仅保证两个 children 的 parent 小于两个 children （正如@chtz 评论的那样）。但不保证左边child比右边小

例如，您的堆可能如下所示（索引：值）：

    0:3
1:5     2:13

按索引顺序打印会得到 3、5、13。这恰好是排序的。但是堆也可能看起来像这样并且仍然是正确的：

     0:3
1:15     2:13

您可能打算做的是实现二叉搜索树。
在这样的树中（假设唯一值）

左边child比parent
右边child比parent大

例如，当插入 (5,1,2,3,20,10,24,12) 时，您会得到这样一棵树：

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

请注意，这样的树在数组中并不紧凑，它经常有空位“_”。
如果你想做这样的树，你需要找到合适的地方来添加一个新成员，使用规则。向上交换，因为不需要堆。
但是为了打印二叉树，必须遍历它。递归打印，先是左边的child，然后是parent，然后是右边的child.
遍历示例树将给出：
_, _, _, 1, _, 2, 3, 5, _, 10, 12, _, 24, _
显然，有必要跟踪实际使用或为空的节点（“_”）；与堆相反。

选择合适大小的树结构时，要考虑最坏的情况，即插入排序后的数据。
例如，如果您插入 1、2、3、5、10，您将得到：

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

因此，为了处理 N 个值，您需要在树中放置 (2<<N)-1 个安全位置。
或者使用由指针动态分配的内存构建的树。
如果你讨厌最坏的情况（很多人都喜欢），那么看看自平衡树。
例如。 Wikipedia.

堆插入未排序

Heap insert is unsorted

c

sorting

heap

insert

depth