從陣列創建最小堆-2種方法

我正在解決有關從陣列構建最小堆的問題。我有兩種方法——第一種是遞回，第二種是使用 while 回圈。遞回方法通過了在線評分器的測驗，但 while 回圈版本似乎不起作用。我在下面的代碼中生成了一些隨機壓力測驗，發現這兩種方法也給出了不同的答案。

我可以知道我的第二種方法有什么錯誤嗎？問題如下：

輸入格式。輸入的第一行包含單個整數??。下一行包含 ?? 空格分隔的整數 ?? _??。

約束。1 ≤ ?? ≤ 100 000；0 ≤ ??，?? ≤ ?? - 1；0 ≤ ?? ₀ , ?? ₁ ,..., ?? _???1 ≤ 109。所有 ?? _??都是不同的。

輸出格式。輸出的第一行應包含單個整數 ?? — 交換的總數。

?? 必須滿足條件 0 ≤ ?? ≤ 4??。接下來的 ?? 行應該包含用于將陣列 ?? 轉換為堆的交換操作。每個交換都由一對整數描述 ??, ?? — 要交換的元素的從 0 開始的索引。在以指定的順序應用所有交換之后，陣列必須變成一個堆，也就是說，對于每個 ??，其中 0 ≤ ?? ≤ ?? - 1 必須滿足以下條件：

1. 如果 2?? 1 ≤ ?? ? 1，則 ?? _?? < ?? _{2?? 1}。
2. 如果 2?? 2 ≤ ?? - 1，則 ?? _?? < ?? _{2?? 2}。

請注意，輸入陣列的所有元素都是不同的。請注意，任何長度最多為 4?? 并且在您的初始陣列變為正確堆之后的任何交換序列都將被評為正確。

我的代碼：

# python3

from random import randint

swaps = []

def sift_down(i, n, data):
    min_index = i
    left_child = 2*i   1
    right_child = 2*i   2
    if left_child < n and data[left_child] < data[min_index]:
        min_index = left_child
    if right_child < n and data[right_child] < data[min_index]:
        min_index = right_child
    if i != min_index:
        swaps.append([i, min_index])
        data[i], data[min_index] = data[min_index], data[i]
        sift_down(min_index, n, data)

def build_heap(data):
    n = len(data)
    for i in range(n//2, -1, -1):
        sift_down(i, n, data)

    return swaps

# wrong answer using while loop instead of recursion
def build_heap2(data):
    swap = []
    for i in range(len(data)-1, 0, -1):
        current_node = i
        prev_node = i // 2 if i % 2 != 0 else i // 2 - 1

        while data[prev_node] > data[current_node] and current_node != 0:
            swap.append((prev_node, current_node))
            data[prev_node], data[current_node] = data[current_node], data[prev_node]
            current_node = prev_node
            prev_node = current_node // 2 if current_node % 2 != 0 else current_node // 2 - 1

    return swap


def main():
    # n = int(input())
    # data = list(map(int, input().split()))
    # assert len(data) == n
    
    while True:
        n = randint(1, 100000)
        data = []
        data2 = []
        for i in range(n):
            data.append(randint(0, 10^9))
        data2 = data.copy()
        
        swaps = build_heap(data)
        swaps2 = build_heap2(data2)
        
        
        if swaps != swaps2:
            print("recursion")
            print(data[0], len(data), len(swaps))
            print("loop:")
            print(data2[0], len(data2), len(swaps2))
            break
        
        else:
            print("success")
    
    swaps = build_heap(data)

    print(len(swaps))
    for i, j in swaps:
        print(i, j)

if __name__ == "__main__":
    main()

uj5u.com熱心網友回復：

你build_heap2實作了一個不正確的想法。它從樹的底部開始（正確），然后在樹的上部尚未堆積的樹上冒泡（錯誤）。情況不妙。它不僅會報告錯誤的交換次數，而且不會總是提供有效的堆。例如，[3, 1, 2, 4, 0]交換后的結果仍然不是堆，因為值 1 最終成為 3 的子代。

目的是在樹的底部構建小堆，并且在父節點的子節點變成堆之后，該父節點中的值被篩選到這些子堆中的任何一個中。這是正確的，因為現在移動值正在一個已經堆積的子樹中移動。結果是這兩個小堆的父級現在是有效堆本身的根。所以在演算法結束時，根將是有效堆的根。

因此，您不需要在樹中向上交換值，而是需要向下交換（選擇值最小的孩子）。

這是更正后的版本：

def build_heap(data):
    swap = []
    # We can start at the deepest parent:
    for i in range(len(data) // 2 - 1, -1, -1):
        current_node = i
        
        while True:
            child_node = current_node * 2   1
            if child_node >= len(data):
                break
            if child_node   1 < len(data) and data[child_node   1] < data[child_node]:
                child_node  = 1
            if data[current_node] < data[child_node]:
                break
            # swap the current value DOWN, with the least of both child values
            swap.append((child_node, current_node))
            data[child_node], data[current_node] = data[current_node], data[child_node]
            current_node = child_node
    return swap

uj5u.com熱心網友回復：

（至少）有兩種方法來構建堆。

O(N) 解決方案從資料集的中間向后作業，確保每個連續元素都是該點的子樹的正確根：

def build_heap_down(data):
    n = len(data)
    for subtree in range(n // 2 - 1, -1, -1):
        sift_down(subtree, n, data)

另一個解決方案是 O(N log N)，只是將每個元素依次添加到一個更大的堆中：

def build_heap_up(data):
    for new_element in range(1, n):
        sift_up(new_element, data)

由于build_heap_up()在最壞的情況下是對數線性的（我認為這是反向排序的輸入），它可能無法滿足您的分配需求，這對交換數量施加了線性限制。盡管如此，一些實驗還是值得做的。也許這就是這個任務的重點。

def sift_up(elt, data):
    while elt > 0:
        parent = (elt - 1) // 2
        if data[parent] <= data[elt]: return
        swap(parent, elt, data)
        elt = parent

def sift_down(elt, limit, data):
    while True:
        kid = 2 * elt   1
        if kid >= limit: return
        if kid   1 < limit and data[kid   1] < data[kid]: kid  = 1
        if data[elt] <= data[kid]: return
        swap(elt, kid, data)
        elt = kid

這里的關鍵見解是兩者都sift_up要求sift_down他們正在使用的陣列是一個堆，除了被篩選的元素。sift_down使用從篩選元素到末尾的陣列，因此在整個陣列上正確執行需要向后作業。sift_up使用從開始到篩選元素的陣列，因此迭代必須向前進行。

據我所知，您build_heap確實如此build_heap_down。雖然它使用遞回，但它與我上面的回圈（以及來自@trincot的版本）做同樣的事情；函式末尾的遞回總是可以使用尾呼叫消除變成一個簡單的回圈。（有些語言會自動執行這種程式轉換，但 Python 不是其中之一。）

你build_heap2的版本不正確，build_heap_up因為它向后作業而不是向前作業。這很容易解決。但是不要指望它會產生相同的堆，更不用說相同的交換串列了。有許多可能的堆可以從給定的數字串列中構建，這就是為什么可以找到一個 O(N) 演算法build_heap而不是 for 的原因sort。

標籤：Python 数组 算法 数据结构 堆

上一篇：使用HoarePartition的快速排序得到不正確的輸出

下一篇：如何遍歷Ruby中的哈希陣列以將每個成員與陣列中的以下成員進行比較？