1

我正在尝试学习和实现一个最小堆来解决一个问题:循环创建双精度并将它们插入到排序数组中,在 C

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

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

听起来像是最小堆要做的事情。

试图

由于在 C 中,数组大小是预先声明的,因此我必须创建一个长度 = 最大双精度数的数组。然后,用值 max_double 填充该数组的所有条目。

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

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

移除:将根节点替换为 max_double,然后与它的两个子节点进行比较,与最小的子节点交换,直到它的两个子节点为 max_double。

问题

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

4

1 回答 1

4

堆不会使数组排序。它只是遵循规则,这意味着在最小堆中,父母总是比他的孩子小。不幸的是,孩子们不必遵守秩序。

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

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

更多解释:

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

Delete : 与数组中的最后一个元素交换 min 删除最后一个元素 现在从顶部开始,比较根与它的孩子,与最小的交换,否则停止。继续与孩子比较,直到满足条件或您没有其他孩子。

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

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

于 2012-09-29T16:07:21.620 回答