Python程式設計：排序算法之堆排序

樹

樹是一種可以遞歸定義的資料結構

樹是由n個節點組成的集合

n=0 空樹

n>0 一個根節點，其他節點分為m個集合，每個集合本身又是一棵樹

一些概念

根節點，葉子節點

樹的深度（高度）

樹的度

孩子節點、父節點

子樹

二叉樹

度不超過2的樹（節點最多有兩個叉）特殊的樹

滿二叉樹

完全二叉樹

二叉樹的存儲方式

• 鍊式存儲
• 順序存儲

父節點和左孩子節點編号關系： i -> 2i+1

父節點和右孩子節點編号關系： i -> 2i+2

堆排序

堆

• 特殊的完全二叉樹
• 大根堆：任一節點都比其孩子節點大
• 小根堆：任一節點都比其孩子節點小

調整

堆排序過程

1. 建立堆
2. 得到堆頂元素，為最大元素
3. 去掉堆頂，将堆最後一個元素放到堆頂，此時可以通過一次調整重新使堆有序
4. 堆頂元素為第二大元素
5. 重複步驟3，直到堆變空

代碼實作

import random

# 調整
def sift(lst, low, high):
    child = 2 * low + 1  # 左孩子
    tmp = lst[low]
    while child < high:  # 孩子在堆裡
        # 如果有右孩子且比左孩子大（找到左右孩子中較大的那個）
        if child + 1 <= high and lst[child] < lst[child+1]:
            child += 1  # 孩子指向右孩子

        # 孩子比父節點大
        if lst[child] > tmp:
            lst[low] = lst[child]  # 孩子調整到父節點上
            low = child  # 孩子成為新的父節點點
            child = 2 * low + 1  # 新的孩子節點
        else:
            break

    lst[low] = tmp  # 根節點放到父親位置

# 堆排序
def heap_sort(lst):
    n = len(lst)  # 清單總長度，也就是最後一個值
    for i in range(n//2 - 1, -1, -1):
        sift(lst, i, n-1)

    # i指向堆的最後
    for i in range(n-1, -1, -1):
        # 根節點取出，最後一個孩子上位
        lst[0], lst[i] = lst[i], lst[0]
        sift(lst, 0, i-1)  # 調整出新根節點

lst = list(range(10))
random.shuffle(lst)
heap_sort(lst)
print(lst)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]