# Heap Sort堆積排序
###### tags: `Algorithm` `Datastruction`

把資料儲存到堆積中，遞降次序即max heap，利用堆積特性，每回取出最大值，再進行重新排序。

python code:

# -*- coding: utf-8 -*-
from __future__ import print_function


def heap_sort(data):
    print('\n<< Heap sort >>')
    print('Number : ', end = '')
    for k in range(1, 11):
        print('%2d ' % data[k], end = '')#讀取data陣列
    print()

    for k in range(60):
        print('-', end = '')

    i = 10
    while i > 0:
        adjust(data, i, 10)#堆積
        i -= 1

    print('\nHeap   : ', end = '')
    for k in range(1, 11):
        print('%2d ' % data[k], end = '')#顯示堆積後結果

    i = 9
    while i > 0:#每次的第一個是最大值(堆積特性)，並與最後位置交換，進行排序
        data[1], data[i+1] = data[i+1], data[1] # 將樹根（最大值）和最後的節點交換
        adjust(data, 1, i) # 再重新調整為堆積樹
        print('\nSorting: ', end = '')
        for k in range(1, 11):
            print('%2d ' % data[k], end = '')
        i -= 1
    print()

    for k in range(60):
        print('-', end = '')

    print('\nFinal sorted data: ', end = '')
    for k in range(1, 11):
        print(data[k], ' ', end = '')#印出最後結果

def adjust(data, i, n): # 將資料調整為堆積樹
    done = 0
    k = data[i]
    j = 2 * i
    while j <= n and done == 0:
        if j < n and data[j] < data[j+1]:
            j += 1
        if k >= data[j]:
            done = 1
        else:
            data[j//2] = data[j]
            j *= 2
    data[j//2] = k

def main():
    data = [0, 27, 7, 80, 5, 67, 18, 62, 24, 58, 25]
    heap_sort(data)

main()