是否可以在不知道最终大小的情况下创建 min/max 堆？

Question

我正在尝试编写一个程序，它将检查简单游戏的状态 space。

该程序将使用启发式函数，我想根据该启发式函数的给定值对最小堆中生成的状态进行排序。

但是堆的大小应该是多少？可以生成的最大状态数是 9！，我认为这是相当多的。如果我不想立即分配那么大的内存 space，该如何管理？

我正在用 C 编写代码。有什么想法吗？

Answer 1

假设您需要为每个状态存储一个整数值。 总大小=9！ * sizeof int (4byte) = 1.384MB。这不是很多！此外，如果没有内部循环来计算状态，则时间复杂度应为 O(10^6) 并且需要几毫秒的时间来计算。

Yes.you 可以在不知道最终结果的情况下创建堆 size.Just 使用链表和动态内存分配。