ROSALIND｜Heap Sort (HS)

發表於 更新於

使用 Heap sort 遞增排序長度為 n 的整數數列。

Given: A positive integer $n \le 10^5$ and an array $A[1..n]$ of integers from $-10^5$ to $10^5$.

Return: A sorted array $A$.

(https://rosalind.info/problems/hs/)

Max heap 的根節點為整個資料結構的最大值。假如我們能夠逐一取出根節點，又能在過程中保持 heap 的結構，那麼數字取出的順序就會與它們的大小次序相符。

因此，max heap 可以用於解決排序問題。實作算法時，會將輸入的數列劃分為堆疊區與排序區。排序區位於數列尾端，按順序擺放取出的根節點；堆疊區則位於數列前端，保持著 heap 結構以存放剩餘的節點。

1
2
3
[   堆疊區   |   排序區   ]
 └─────────┘  └─────────┘
   Max Heap   Sorted List

在起步階段，整個數列都是堆疊區。取出的根節點不會放到額外的空間，而是與堆疊區末端的數字交換。交換數字後，堆疊區的 heap 結構可能會受到影響，所以要從根節點執行一次 floyd’s method 的步驟，恢復 heap 的特性。

1
2
3
4
5
6
7
8
9
10
11
# 一開始全部都是堆疊區
[   5   4   3   2   1   ]

# 根節點與最後節點互換
[   1   4   3   2   5   ]
   └─────────────┘ └─┘
        堆疊區     排序區
      (需要修復)  (已排序)

# 修復堆疊區（重複取出直到完成排序）
[   4   2   3   1   5   ]

這行為相當於從堆疊區取出一個數字放到排序區，所以堆疊區與排序區的範圍會隨著取出節點而消長。一旦取出堆疊區的所有數字，整個數列只剩下排序區，也同時在原數列完成排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def sift_down(l: list[int], i: int, n: int):
    # 因為堆疊區會逐漸變小，所以新增 n 來限制範圍
    candidates = [idx for idx in (i, 2 * i + 1, 2 * i + 2) if idx < n]
    largest = max(candidates, key=lambda x: l[x])
    if largest != i:
        l[largest], l[i] = l[i], l[largest]
        sift_down(l, largest ,n)
def heapify(l: list[int]) -> list[int]:
    n = len(l)
    for idx in range(n // 2 - 1, -1, -1):
        sift_down(l, idx, n)
    return l
def hs(l: list[int]) -> list[int]:
    hp = heapify(l)
    for end in range(len(l) - 1, 0, -1):
        hp[end], hp[0] = hp[0], hp[end] # 根節點與最後一個節點交換
        sift_down(hp, 0, end) # 恢復 heap 特性
    return hp