为什么 siftdown 在 heapsort 中工作，而不是 siftup？

Question

我有一个编程任务如下：您将需要仅使用 O(n) 次交换将数组转换为堆，如讲座中所述。请注意，在此问题中您需要使用 min-heap 而不是 max-heap。输出的第一行应该包含一个整数 m——交换的总数。 m 必须满足条件 0 ≤ m ≤ 4n。接下来的 m 行应该包含用于将数组 a 转换为堆的交换操作。每个交换由一对整数 i,j 描述——要交换的元素的从 0 开始的索引

我已经通过与 parent 的值进行比较来实现了一个使用筛选技术的解决方案，该值给出了小文本情况的解决方案，当数组中的整数数量小于 10 时，通过手动检查验证，但是它无法通过以 100000 个整数作为输入的测试用例。这是

的代码


class HeapBuilder:
    def __init__(self):
        self._swaps = [] #array of tuples or arrays
        self._data = []

    def ReadData(self):
        n = int(input())
        self._data = [int(s) for s in input().split()]
        assert n == len(self._data)

    def WriteResponse(self):
        print(len(self._swaps))
        for swap in self._swaps:
            print(swap[0], swap[1])

    def swapup(self,i):
        if i !=0:
            if self._data[int((i-1)/2)]> self._data[i]:
                self._swaps.append(((int((i-1)/2)),i))
                self._data[int((i-1)/2)], self._data[i] = self._data[i],self._data[int((i-1)/2)]
                self.swapup(int((i-1)/2))

    def GenerateSwaps(self):
        for i in range(len(self._data)-1,0,-1):
            self.swapup(i)

    def Solve(self):
        self.ReadData()
        self.GenerateSwaps()
        self.WriteResponse()

if __name__ == '__main__':
    heap_builder = HeapBuilder()
    heap_builder.Solve()

另一方面，我已经使用具有类似比较过程的筛选技术实现了堆排序，并且这个东西已经通过了每个测试用例。以下是此方法的代码

class HeapBuilder:
    def __init__(self):
        self._swaps = [] #array of tuples or arrays
        self._data = []

    def ReadData(self):
        n = int(input())
        self._data = [int(s) for s in input().split()]
        assert n == len(self._data)

    def WriteResponse(self):
        print(len(self._swaps))
        for swap in self._swaps:
            print(swap[0], swap[1])

    def swapdown(self,i):
        n = len(self._data)
        min_index = i
        l = 2*i+1 if (2*i+1<n) else -1 
        r = 2*i+2 if (2*i+2<n) else -1 

        if l != -1 and self._data[l] < self._data[min_index]:
            min_index = l

        if r != - 1 and self._data[r] < self._data[min_index]:
            min_index = r

        if i != min_index:
            self._swaps.append((i, min_index))
            self._data[i], self._data[min_index] = \
                self._data[min_index], self._data[i]
            self.swapdown(min_index)

    def GenerateSwaps(self):
        for i in range(len(self._data)//2 ,-1,-1):
            self.swapdown(i)

    def Solve(self):
        self.ReadData()
        self.GenerateSwaps()
        self.WriteResponse()

if __name__ == '__main__':
    heap_builder = HeapBuilder()
    heap_builder.Solve()

有人可以解释一下 sift/swap up 方法有什么问题吗？

Answer 1

尝试从底部 "swapping up" 构建堆并不总是有效。结果数组不一定是有效的堆。例如，考虑这个数组：[3,6,2,4,5,7,1]。视为树即：

       3
    4     2
   6 5   7 1

您的算法从最后一项开始，向上交换到根。所以你把 1 和 2 交换，然后你把 1 和 3 交换。这给你：

       1
    4     3
   6 5   7 2

然后您继续处理其余项目，其中 none 必须移动。

结果是无效堆：最后一项 2 应该是 3 的父项。

这里的关键是向上交换方法假定当您处理完 a[i] 时，最终位于该位置的项目位于其最终位置。将其与允许重复调整堆中较低项目的向下交换方法进行对比。

为什么 siftdown 在 heapsort 中工作，而不是 siftup？

why is siftdown working in heapsort, but not siftup?

python-3.x

data-structures

heapsort

binary-heap