c++ - 构建堆原则——用 C++ 实现

Question

我的家庭作业有些麻烦。我被要求使用 C++ 中的堆来实现优先级队列。

在搜索创建堆的代码示例时，我在这个定义中遇到了很多次：

表示堆的数组A是具有两个属性的数组：

– length，数组中的元素个数

– heap-size，存储在数组中的堆元素的数量

所以我的问题是：什么是A？我是否需要自己实现它（假设创建一个包含 3 个字段的类堆 - 元素数组、长度和堆大小）？

我只是不知道如何开始。

Answer 1

二叉堆数据结构通常被绘制为具有某些属性的二叉树，但通常使用普通数组来实现。这样做的原因是数组版本比显式二叉树使用更少的内存并且更容易操作。因此，您看到的数组A是保存堆中所有值的数组。

您看到的两个字段表示该数组的原始总大小（长度），它跟踪可用存储空间的数量，以及您实际使用的该数组中的元素数量（堆大小）。当您将一个元素插入堆中时，您需要确保它存在空间，可能将数组重新分配为更大并复制现有元素，然后需要运行冒泡操作来插入新元素入堆。

但是，通常情况下，您会通过将堆分层放在动态数组（如 C++std::vector或 Java ）之上来回避维护数组和这两个字段的逻辑ArrayList。这样，跟踪存储空间和增长阵列的逻辑就会自动为您处理。

根据分配参数，由于这是在 C++ 中完成的，因此您可能需要查看标题中的std::make_heap、std::push_heap和std::pop_heap算法。<algorithm>它们使得在现有容器（如std::vector. 事实上，这就是std::priority_queue类的典型实现方式。

如果您需要自己实现堆操作，您可能需要查看此作业讲义中给出的二进制堆的描述，这似乎与您获得的作业非常匹配。

希望这可以帮助！