我正在尝试学习和实现一个最小堆来解决一个问题:循环创建双精度并将它们插入到排序数组中,在 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。
问题
我对所有这些都使用了正确的方法吗?