有人听说过这种堆修复技术吗：SloppyHeapSort吗？它使用了一种“松散的”下滑方式。基本上，它将要修复的元素移动到堆的底部（不与其子节点进行比较），通过用其较大的子节点替换它来实现，直到它达到底部。然后调用sift-up函数直到它到达正确的位置。 在大小为n的堆中，这只需要稍微超过lg n次比较。
然而，这不能用于堆构建，只能用于堆修复。为什么呢？我不明白如果你想建立一个堆为什么它不起作用。
然而，这不能用于堆构建，只能用于堆修复。为什么呢？我不明白如果你想建立一个堆为什么它不起作用。
2个回答
3
如果正确部署，该算法肯定可以作为堆构建算法的一部分使用。但是，在堆构建期间，正在修复的子堆的根不是数组的开头，这会影响sift-up的实现（需要在到达当前数组元素时停止，而不是继续到堆底部）。
应该注意的是，该算法与标准堆修复算法具有相同的渐进性能；然而，它可能比较少涉及比较。部分原因是，标准堆修复算法在将堆的根（最大元素）与堆数组中的最后一个元素交换后调用。
最后一个元素不一定是堆中最小的元素，但它肯定接近底部。交换后，标准算法将最多向下移动交换的元素log2N次，每个步骤需要两个比较；由于该元素很可能属于堆底部附近，大多数时间执行的比较数量将最大。但有时只会执行两或四次比较。
相反，“松散”算法首先从堆顶将“空洞”移动到接近底部的某个位置（log2N次比较），然后将最后一个元素上移，直到找到其位置，这通常只需要少量比较（但在最坏情况下可能需要接近log2N次比较）。
现在，在
尽管“松散”算法（可能）提高了元素比较的数量，但它增加了元素移动的数量。经典算法最多执行log2N个交换，而松散算法至少执行log2N个交换，以及sift-up期间的其他交换。（在两种情况下，可以通过在知道其实际位置之前不插入新元素来将交换改进为移动，从而将内存存储的数量减半。）
补充一点，我无法找到您提到的“松散”算法的任何参考资料。总的来说，当询问提出的算法时，通常最好包含链接。
应该注意的是，该算法与标准堆修复算法具有相同的渐进性能；然而，它可能比较少涉及比较。部分原因是，标准堆修复算法在将堆的根（最大元素）与堆数组中的最后一个元素交换后调用。
最后一个元素不一定是堆中最小的元素，但它肯定接近底部。交换后，标准算法将最多向下移动交换的元素log2N次，每个步骤需要两个比较；由于该元素很可能属于堆底部附近，大多数时间执行的比较数量将最大。但有时只会执行两或四次比较。
相反，“松散”算法首先从堆顶将“空洞”移动到接近底部的某个位置（log2N次比较），然后将最后一个元素上移，直到找到其位置，这通常只需要少量比较（但在最坏情况下可能需要接近log2N次比较）。
现在，在
heapify的情况下，堆修复不是使用子堆中的最后一个元素，而是使用从原始向量中获取的以前未见过的元素。这实际上并没有改变平均性能分析，因为如果您从随机元素开始堆修复，而不是从可能很小的元素开始，那么需要进行的sift-down操作的预期数量仍接近最大值。 （一半堆位于最后一级，因此对于随机元素需要最大数量的筛选次数的概率为一半。）尽管“松散”算法（可能）提高了元素比较的数量，但它增加了元素移动的数量。经典算法最多执行log2N个交换，而松散算法至少执行log2N个交换，以及sift-up期间的其他交换。（在两种情况下，可以通过在知道其实际位置之前不插入新元素来将交换改进为移动，从而将内存存储的数量减半。）
补充一点，我无法找到您提到的“松散”算法的任何参考资料。总的来说，当询问提出的算法时，通常最好包含链接。
- rici
1
通常称为自底向上堆排序。 - David Eisenstat
1
有一种线性时间的算法可以构建堆。我相信作者的意思是使用这种方法来构建堆不够高效，存在更好的算法。当然，您可以使用所描述的策略逐个添加元素来构建堆-只是您可以做得更好。
- Ivaylo Strandjev
2
我同意，有可能做得更好。但我也在想，这种不太规范的技术是否与堆结构和常规堆修复函数有关。如果它期望堆已经处于合理正确的形式，那么它就不能用来构建堆，对吧？ - user3270760
不，我不这么认为。你可以使用这种技术来插入任何堆，因此它可以用来构建堆。 - Ivaylo Strandjev
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 43 堆排序的直观理解是什么？
- 5 堆排序的空闲时间
- 3 堆排序时间复杂度深入理解
- 76 为什么不总是使用堆排序
- 18 堆排序的下界是多少？
- 6 1-ary堆排序？
- 3 高效缓存的堆排序堆。
- 121 快速排序与堆排序
- 3 堆排序算法的问题
- 53 快速排序相对于堆排序的优越性