为heapsort优化堆结构
Optimizing heap structure for heapsort
我正在使用堆实现堆排序。为此，将插入每个要排序的值。插入方法调用 heapifyUp()（又名 siftUp），所以这意味着每次插入另一个值时都会调用 heapifyUp。这是最有效的方法吗？
另一个想法是插入所有元素，然后调用heapifyUp。我想每个人都必须调用 heapifyUp 吗？这样做更好吗？
插入每个元素将在 O(n log n) 时间内构建堆。如果将所有元素添加到一个数组然后重复调用 heapifyUp().
也是一样的
Floyd's Algorithm 在 O(n) 时间内自底向上构建堆。这个想法是，您采用任意顺序的数组，然后从中间开始，将每个项目 down 筛选到适当的位置。算法是：
for i = array.length/2 downto 0
{
siftDown(i)
}
您从中间开始，因为数组中的最后 length/2 项是叶子。他们不能被筛选下来。通过从中间向上移动，您可以减少必须移动的项目数量。
差异示例
下面的示例将一个包含 7 个项目的数组变成一个堆，显示了所完成工作量的差异。
heapifyUp()方法
[7,5,6,1,2,3,4] (starting state)
从最后开始，向上冒泡。
将 4 移动到正确的位置
[7,5,4,1,2,3,6]
[4,5,7,1,2,3,6]
将 3 移到原位
[4,5,3,1,2,7,6]
[3,5,4,1,2,7,6]
将 2 移到原位
[3,2,4,1,5,7,6]
[2,3,4,1,5,7,6]
将 1 移到它的位置
[2,1,4,3,5,7,6]
[1,2,4,3,5,7,6]
堆现在井然有序。换了8次，还得勾选4、2、1
弗洛伊德算法
[7,5,6,1,2,3,4] (starting state)
从中间点开始向下筛选。在一个从 0 开始的 7 项数组中，中间点是 3.
将 1 移到它的位置
[7,5,6,1,2,3,4] (no change. Remember, we're sifting down)
将 6 移到原位
[7,5,3,1,2,6,4]
将 5 移到原位
[7,1,3,5,2,6,4]
[7,1,3,4,2,6,5]
将 7 移到原位
[1,7,3,5,2,6,4]
[1,2,3,5,7,6,4]
我们完成了。交换了 5 次，没有其他要检查的东西。
我正在使用堆实现堆排序。为此，将插入每个要排序的值。插入方法调用 heapifyUp()（又名 siftUp），所以这意味着每次插入另一个值时都会调用 heapifyUp。这是最有效的方法吗？
另一个想法是插入所有元素，然后调用heapifyUp。我想每个人都必须调用 heapifyUp 吗？这样做更好吗？
插入每个元素将在 O(n log n) 时间内构建堆。如果将所有元素添加到一个数组然后重复调用 heapifyUp().
Floyd's Algorithm 在 O(n) 时间内自底向上构建堆。这个想法是，您采用任意顺序的数组，然后从中间开始，将每个项目 down 筛选到适当的位置。算法是：
for i = array.length/2 downto 0
{
siftDown(i)
}
您从中间开始，因为数组中的最后 length/2 项是叶子。他们不能被筛选下来。通过从中间向上移动，您可以减少必须移动的项目数量。
差异示例
下面的示例将一个包含 7 个项目的数组变成一个堆，显示了所完成工作量的差异。
heapifyUp()方法
[7,5,6,1,2,3,4] (starting state)
从最后开始，向上冒泡。
将 4 移动到正确的位置
[7,5,4,1,2,3,6]
[4,5,7,1,2,3,6]
将 3 移到原位
[4,5,3,1,2,7,6]
[3,5,4,1,2,7,6]
将 2 移到原位
[3,2,4,1,5,7,6]
[2,3,4,1,5,7,6]
将 1 移到它的位置
[2,1,4,3,5,7,6]
[1,2,4,3,5,7,6]
堆现在井然有序。换了8次，还得勾选4、2、1
弗洛伊德算法
[7,5,6,1,2,3,4] (starting state)
从中间点开始向下筛选。在一个从 0 开始的 7 项数组中，中间点是 3.
将 1 移到它的位置
[7,5,6,1,2,3,4] (no change. Remember, we're sifting down)
将 6 移到原位
[7,5,3,1,2,6,4]
将 5 移到原位
[7,1,3,5,2,6,4]
[7,1,3,4,2,6,5]
将 7 移到原位
[1,7,3,5,2,6,4]
[1,2,3,5,7,6,4]
我们完成了。交换了 5 次，没有其他要检查的东西。