c - 堆插入未排序

Question

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

(请注意，x、y、z 和深度(此处未使用)均以 int 形式存储在实体结构中。

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 所评论的)。但并不能保证左 child 小于右 child 。

例如，您的堆可能如下所示(索引:值):

    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   _  _

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

在选择适当大小的树结构时，请考虑最坏的情况，即插入排序的数据。
例如，如果插入 1, 2, 3, 5, 10，您将得到:

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

因此，为了处理 N 值，您需要 (2<<N)-1树上安全的地方。
或者使用由动态分配的内存和指针构建的树。
如果您讨厌最坏的情况(很多人都这样做)，那么看看自平衡树。
例如。 Wikipedia .