有没有人听说过这种堆修复技术:SloppyHeapSort？它使用“草率”筛选方法。基本上，它将要修复的元素移动到堆的底部(不将其与其子元素进行比较)，将其替换为较大的子元素，直到它到达底部。然后，调用 sift-up 直到它到达正确的位置。这仅进行了 lg n 次比较(在大小为 n 的堆中)。
但是，这不能用于堆构建，只能用于堆修复。为什么是这样？我不明白如果你试图建立一个堆为什么它不起作用。
最佳答案
如果部署得当，该算法当然可以用作堆构造算法的一部分。稍微复杂一点，在堆构建时，被修复的子堆的根不是数组的开头，影响了sift-up的实现(需要在到达数组当前元素时停止，而不是继续到堆的底部)。
需要注意的是，该算法具有与标准堆修复算法相同的渐近性能；然而，它可能涉及较少的比较。在某种程度上，这是因为在将堆的根(最大元素)交换为堆数组中的最后一个元素之后，会调用标准堆修复算法。
最后一个元素不一定是堆中最小的元素，但肯定有可能靠近底部。交换后，标准算法会将交换后的元素向下移动 log2N 次，每一步都需要进行两次比较；因为元素很可能属于堆底部附近，所以大多数情况下将执行最大数量的比较。但有时，可能只进行两到四次比较。
相反，“草率”算法首先将“洞”从堆的顶部移动到靠近底部的某个位置(log2N 比较)，然后将最后一个元素向上移动直到找到它，这通常只需要进行几次比较(但在最坏的情况下，可以进行近 log2N 的比较)。
现在，在 heapify 的情况下，堆修复不是使用子堆中的最后一个元素，而是使用从原始向量中提取的先前未见过的元素。这实际上不会对平均性能分析产生太大影响，因为如果您使用随机元素而不是可能较小的元素开始堆修复，那么预期的筛选操作次数仍然接近最大值。 (堆的一半位于最后一层，因此需要对随机元素进行最大筛选次数的概率为二分之一。)
虽然草率算法(可能)提高了元素比较的次数，但它增加了元素移动的次数。经典算法最多执行 log2N 次交换，而马虎算法至少执行 log2N 次交换，再加上筛选期间的额外交换。 (在这两种情况下，可以通过在知道其实际位置之前不插入新元素来改进交换以移动，从而将内存存储的数量减半。)
作为附言，我找不到对您的“草率”算法的任何引用。总的来说，当询问建议的算法时，通常最好包含一个链接。
关于algorithm - 草率堆排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26468370/