c - 在 C 中实现最小堆 - 使用数组？

Question

我正在尝试学习和实现最小堆来解决问题:Loop that creates doubles and insert them into sorted array, in C

基本上，我从一组 double 开始，从小到大排序。然后，我生成 double (可能是随机的)并且必须将新生成的 double 添加到集合中，同时保持它排序。此外，每次我插入一个 double 时，我都会从集合中删除最小的 double 。

(edit - 集合不必完全排序。目标是能够在每次插入 double 后查找并删除最小元素。保持集合排序是我的第一个天真的解决方案。)

听起来像是创建最小堆的目的。

尝试

因为在 C 中，数组大小是预先声明的，所以我必须创建一个长度 = 最大 double 的数组，我将最终得到。然后，用值 max_double 填充该数组的所有条目。

使用此处描述的方法作为指南:http://opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html ，我可以创建函数来向这个数组中插入和删除值。

插入:用数字替换数组的最后一个条目(永远是 max_double)。然后不断与父节点的值进行交换，直到父节点的值小于新增的值。

去除:将根节点替换为max_double，然后与它的两个 child 比较，与最小的 child 交换，直到它的两个 child 为max_double。

问题

我对所有这些都使用了正确的方法吗？

Answer 1

堆不会使数组排序。它只是遵循规则，这意味着在最小堆中， parent 总是比他的 child 小。不幸的是， children 不必井井有条。

如果您想在数组中实现堆，wiki 上有一个很棒的页面。

http://en.wikipedia.org/wiki/Binary_heap

更多解释:

插入: 将元素添加到数组的末尾(不替换!) 如果顺序正确停止，则将元素与父元素进行比较(i-1/2)。 否则交换并再次执行步骤 2。 (记得更新当前索引)

删除: 将 min 与数组中的最后一个元素交换 删除最后一个元素 现在从顶部开始，将根与其子节点进行比较，与最小的交换，否则停止。 不断与 child 比较，直到条件满足或您没有其他 child 为止。

对于从 0 开始的索引，父项位于 floor((i-1)/2)，子项位于 2i+1 和 2i+2

还有一件事，我建议使用双端队列来存储你的 double 。