數(shù)據(jù)結(jié)構(gòu)堆
- 是一顆完全二叉樹。完全二叉樹：設(shè)二叉樹的深度為h嗦篱，除了第h層以外，前面的每一層的節(jié)點數(shù)都達(dá)到最大幌缝，并且第h層的葉子都集中在最左邊。
- 所有非終端（有葉子）節(jié)點的值均不小于（或不大于）其左涵卵、右孩子的值浴栽。前者叫大頂堆轿偎，后者叫小頂堆典鸡。
堆排序思想
利用堆數(shù)據(jù)結(jié)構(gòu)的堆頂肯定是最大值（或最小值）坏晦，則可以取出堆頂元素椿每，然后對剩下的元素重新構(gòu)造大頂堆（或小頂堆）后英遭，繼續(xù)取出堆頂元素间护，知道所有元素被取完。則取出的元素會按照順序排列汁尺。
圖解堆排序過程
alist = [16,7,3,20,17,8]為例
-
首先根據(jù)列表構(gòu)造一個完全二叉樹
來自百度百科.png -
構(gòu)造初始堆，從葉子節(jié)點往上層調(diào)整
來自百度百科.png -
發(fā)現(xiàn)20和16交換位置后多律，不滿足堆的性質(zhì)，所以重新調(diào)整
來自百度百科.png -
這樣就得到了大頂堆狼荞，讓堆頂元素和最后一個葉子節(jié)點交換位置
來自百度百科.png -
排除元素20后辽装，重新構(gòu)造堆結(jié)構(gòu)相味。直到所有元素排除完拾积。
來自百度百科.png
來自百度百科.png
python實現(xiàn)
#!/usr/bin/python
# encoding: utf-8
# 從start到end的位置構(gòu)造一個大頂堆
def siftAdjust(alist, start, end):
# start位置作為堆頂
root = start
# 左葉子
while True:
# child初始為左邊的子節(jié)點
child = root * 2 + 1
if child >= end:
break
# 比較左右葉子節(jié)點的大小丰涉，找出最大的那一個
if child + 1 <= len(alist) - 1 and alist[child] < alist[child + 1]:
child = child + 1
# 把最大的子節(jié)點和根節(jié)點交換位置
if alist[root] < alist[child]:
alist[root], alist[child] = alist[child], alist[root]
# 調(diào)整過后，需要更新根節(jié)點一死，以防交換位置后肛度，子樹不再是堆結(jié)構(gòu)
root = child
# 若沒有調(diào)整，則直接退出
else:
break
def heapSort(alist):
# 從最后一個有子節(jié)點的位置開始調(diào)整大頂堆
first = (len(alist) - 2) // 2
# 初始化一個大頂堆
for i in range(first, -1, -1):
siftAdjust(alist, i, len(alist) - 1)
# 第i趟排序
for i in range(len(alist)-1,0,-1):
# 把第一個位置堆頂與最后一個位置交換
alist[0],alist[i] = alist[i],alist[0]
# 調(diào)整堆結(jié)構(gòu)
siftAdjust(alist,0,i-1);
if __name__ == '__main__':
a = [4,10,7,9,5,3,1,2,8,6]
heapSort(a)
print(a)
