調(diào)用關(guān)系：
heap_sort
/ |
build_max_heap_by_down_adjust |
\ |
maxheap_down_adjust
堆排序python實(shí)現(xiàn)：
def heap_sort(array: list[int]) -> None:
"""
原地堆排序 (大頂堆實(shí)現(xiàn)的從小到大排序)
"""
# egde case
if len(array) <= 1:
return
# 1. 建堆. 建堆有2種思路：down_adjust 和 up_adjust衩侥。詳見(jiàn)下文說(shuō)明
build_max_heap_by_down_adjust(array)
# build_max_heap_by_up_adjust(array)
# 2. loop to sort: 將array首尾換位置，最大值到最后矛物，然后再maxheap_down_adjust
for i in range(len(array) - 1, 0, -1):
array[i], array[0] = array[0], array[i]
maxheap_down_adjust(array, 0, i - 1)
return
def build_max_heap_by_down_adjust(array: list[int]) -> None:
# 構(gòu)建大頂堆 by_down_adjust
# down_adjust從最后一個(gè)非葉子結(jié)點(diǎn)起（也可以從葉子結(jié)點(diǎn)起茫死，但沒(méi)必要，因?yàn)槿~子本身已經(jīng)是合法的堆結(jié)構(gòu)）履羞，
# 倒序地通過(guò)maxheap_down_adjust構(gòu)建每個(gè)子大頂堆
lenth = len(array)
for i in range(lenth // 2 - 1, -1, -1):
# i as maxheap root_index
maxheap_down_adjust(array, i, lenth - 1)
print(f"heap built as: {array}")
return
def maxheap_down_adjust(array: list[int], root_index: int, end_index: int) -> None:
"""
maxheap_down_adjust 以root_index為根的一個(gè)大頂堆的向下調(diào)整峦萎。
【前提條件是root的左右結(jié)點(diǎn)已經(jīng)是大頂堆根屡久，這樣才能做到root只需要關(guān)注自己的左右結(jié)點(diǎn)】
:param array: 待排序的數(shù)組，可通過(guò)下標(biāo)推斷parent node和child node
:param root_index: 大頂堆根的index
:param end_index: 推斷parent node和child node時(shí)爱榔，最后一個(gè)合法index
:return: None
"""
# down_adjust過(guò)程：
# 1. if 樹(shù)根（array[root_index]）的左子結(jié)點(diǎn)存在被环，且左子結(jié)點(diǎn)值 > 樹(shù)根，將樹(shù)根與左子結(jié)點(diǎn)進(jìn)行值交換, and build_max_heap(array, left_child_index)
# 2. if 樹(shù)根（array[root_index]）的右子結(jié)點(diǎn)存在详幽，且右子結(jié)點(diǎn)值 > 樹(shù)根筛欢，將樹(shù)根與右子結(jié)點(diǎn)進(jìn)行值交換, and build_max_heap(array, right_child_index)
if root_index > end_index:
raise ValueError(f"err: root_index({root_index}) > end_index({end_index})")
left_child_index, right_child_index = 2 * root_index + 1, 2 * root_index + 2
if left_child_index <= end_index:
left_child_value = array[left_child_index]
if left_child_value > array[root_index]:
# swap value of root and left_child
array[left_child_index], array[root_index] = array[root_index], array[left_child_index]
# maxheap_down_adjust left_child recursively
maxheap_down_adjust(array, left_child_index, end_index)
if right_child_index <= end_index:
right_child_value = array[right_child_index]
if right_child_value > array[root_index]:
# swap value of root and right_child
array[root_index], array[right_child_index] = array[right_child_index], array[root_index]
# maxheap_down_adjust right_child recursively
maxheap_down_adjust(array, right_child_index, end_index)
return
def build_max_heap_by_up_adjust(array: list[int]) -> None:
# 構(gòu)建大頂堆 by_up_adjust
# up_adjust從首個(gè)結(jié)點(diǎn)起，
# 順序地對(duì)每個(gè)節(jié)點(diǎn)使用maxheap_up_adjust進(jìn)行堆調(diào)整
lenth = len(array)
for i in range(lenth):
maxheap_up_adjust(array, i)
print(f"heap built as: {array}")
return
def maxheap_up_adjust(array: list[int], bottom_index: int) -> None:
child_index = bottom_index
parent_index = (child_index - 1) // 2
if parent_index >= 0 and array[child_index] > array[parent_index]:
# swap parent and child
array[child_index], array[parent_index] = array[parent_index], array[child_index]
# 繼續(xù)以 parent_index 為 bottom 節(jié)點(diǎn)進(jìn)行向上調(diào)整
maxheap_up_adjust(array, parent_index)
test_list = [134, 5, 565, 35, 676, 3, 2, 1, 4, 5]
heap_sort(test_list)
print(test_list)
down_adjust和up_adjust
down_adjust（向下調(diào)整）：
down_adjust將調(diào)整起點(diǎn)視為堆頂元素妒潭，從堆頂開(kāi)始向下調(diào)整堆結(jié)構(gòu)悴能，以維護(hù)堆的性質(zhì)（大頂堆或小頂堆）。這個(gè)操作通常在堆頂元素被移除或替換時(shí)使用雳灾，例如在堆排序算法中漠酿，將堆頂元素與最后一個(gè)元素交換后，需要通過(guò)down_adjust重新調(diào)整堆結(jié)構(gòu)谎亩。
down_adjust的具體步驟如下：
- 從堆頂元素開(kāi)始炒嘲，找到其左右孩子中較大（大頂堆）或較小（小頂堆）的一個(gè)匈庭；
- 如果當(dāng)前節(jié)點(diǎn)比較大（大頂堆）或較蟹蛲埂（小頂堆）的孩子還要大（大頂堆）或小（小頂堆）阱持，則不需要調(diào)整夭拌，結(jié)束；
- 否則衷咽，將當(dāng)前節(jié)點(diǎn)與較大（大頂堆）或較懈氡狻（小頂堆）的孩子交換；繼續(xù)向下調(diào)整镶骗，直到葉子節(jié)點(diǎn)或不需要交換為止桶现。
up_adjust（向上調(diào)整）：
up_adjust將調(diào)整起點(diǎn)視為堆底元素，從堆底開(kāi)始向上調(diào)整堆結(jié)構(gòu)鼎姊，以維護(hù)堆的性質(zhì)（大頂堆或小頂堆）骡和。這個(gè)操作通常在向堆中插入新元素時(shí)使用，例如在構(gòu)建堆或?qū)崿F(xiàn)優(yōu)先級(jí)隊(duì)列時(shí)相寇，需要通過(guò)up_adjust調(diào)整堆結(jié)構(gòu)慰于。
up_adjust的具體步驟如下：
- 從新插入的元素開(kāi)始，找到其父節(jié)點(diǎn)唤衫；
- 如果當(dāng)前節(jié)點(diǎn)比其父節(jié)點(diǎn)要衅旁（大頂堆）或大（小頂堆），則不需要調(diào)整战授，結(jié)束页藻；
- 否則桨嫁，將當(dāng)前節(jié)點(diǎn)與其父節(jié)點(diǎn)交換；繼續(xù)向上調(diào)整份帐，直到根節(jié)點(diǎn)或不需要交換為止璃吧。
