資料結構-學習筆記-堆排序

堆排序

1、二叉樹

1.1 二叉樹

• 每個節點最多有兩個子節點，且左右子樹的順序不能任意颠倒

1.2滿二叉樹

• 深度為n, 由2^(n-1)個節點構成的二叉樹為滿二叉樹

1.3完全二叉樹

• 完全二叉樹是由滿二叉樹而引出來的，設二叉樹的深度為n, 如果1->(n-1)層均是滿節點的，即為一個滿二叉樹，且第n層的所有節點都連續集中在左側

2、堆(完全二叉樹)

• 大根堆: 每一個父節點都比其子節點大
• 小根堆: 每一個父節點都比其子節點小

3、堆排序過程

1.構造堆
    2.堆頂元素為最大元素
    3.去掉堆頂元素，将最後一個元素放置堆頂，通過一次調整重新使堆有序
    4.獲得第二大元素
    5.重複步驟3，直至堆中無元素
           

• 複雜度 O(nlogn), 每一層向下logn，共有n層

# 調整函數
def sift(li,top,end): # 一次調整  要看堆頂的元素究竟該放置在哪個位置
    tmp = li[top] # 堆頂元素
    i = top
    j = 2*i + 1
    while j <= end: # 向下調整時，位置有數，不為空
        if j+1 <= end and li[j+1] > li[j]: # 如果有右節點，判斷子節點中誰的元素較大  
            j = j+1 # 指向右節點
        if li[j] > tmp: # 子節點元素大于父節點元素，取代
            li[i] = li[j] 
            i = j
            j = 2*i + 1
        else:
            li[i] = tmp
            break
    else: 
        li[i] = tmp

def heap_sort(li):
    
    # 1、構造堆
    n = len(li)
    for i in range((n-2)//2,-1,-1):
        sift(li,i,n-1)
    
    # 2、挨個出數
    for i in range(n-1,-1,-1):
        li[0],li[i] = li[i],li[0]
        sift(li,0,i-1)

li = [2,4,3,6,9,1,7,8,5]
heap_sort(li)
print(li)

# result
[1, 2, 3, 4, 5, 6, 7, 8, 9]