本文實例講述了Python數據結構與算法之完全樹與最小堆。分享給大家供大家參考，具體如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
# 完全樹 最小堆class CompleteTree(list): def siftdown(self,i): """ 對一顆完全樹進行向下調整，傳入需要向下調整的節點編號i 當刪除了最小的元素后，當新增加一個數被放置到堆頂時， 如果此時不符合最小堆的特性，則需要將這個數向下調整，直到找到合適的位置為止""" n = len(self) # 當 i 節點有兒子（至少是左兒子時），并且有需要調整時，循環執行 t = 0 while i*2+1<n: # step 1：從當前結點，其左兒子，其右兒子中找到最小的一個，將其編號傳給t if self[i] > self[i*2+1]: t = i*2+1 else: t = i # 如果有右兒子，則再對右兒子進行討論 if i*2+2<n: if self[t] > self[i*2+2]: t = i*2+2 # step 2：把最小的結點中的元素和結點i的元素交換 if t != i: self[t],self[i] = self[i],self[t] i = t # 更新i為剛才與它交換的兒子結點的編號，以便接下來繼續向下調整 else: break # 說明當前父結點已經比兩個子結點要小，結束調整 def siftup(self,i): """ 對一棵完全樹進行向上調整，傳入一個需要向上調整的結點編號i 當要添加一個新元素后，對堆底（最后一個）元素進行調整 """ if i==0: return n = len(self) if i < 0: i += n # 注意，由于堆的特性，不需要考慮左兒子結點的情況 # 由于父結點絕對比子結點小所以只需要比較一次 while i!=0: if self[i]<self[(i-1)/2]: self[i],self[(i-1)/2] = self[(i-1)/2],self[i] else: break i = (i-1)/2 # 更新i為其父結點編號，從而便于下一次繼續向上調整 def shufflePile(self): """ 在當前狀態下，對樹調整使其成為一個堆 """ # 從"堆底"往"堆頂"進行向下調整，使得最小的元素不斷上升 # 這樣可以使得i結點以下的堆是局部最小堆 for i in range((len(self)-2)/2,-1,-1): # n/2,...,0 self.siftdown(i) def deleteMin(self): """ 刪除最小元素 """ t = self[0] # 用一個臨時變量記錄堆頂點的 self[0] = self[-1] # 將堆的最后一個點賦值到堆頂 self.pop() # 刪除最后一個元素 self.siftdown(0) # 向下調整 return t def heapsort(self): """ 對堆中元素進行堆排序操作 """ n = len(self) s = [] while n>0: s.append(self.deleteMin()) n -= 1 # 由于堆中的元素已全部彈出，將排序好的元素拼接到原來的堆中 self.extend(s)if __name__=="__main__": a = [99,5,36,7,22,17,92,12,2,19,25,28,1,46] ct = CompleteTree(a) print ct>>> [99, 5, 36, 7, 22, 17, 92, 12, 2, 19, 25, 28, 1, 46] ct.shufflePile() print ct>>> [1, 2, 17, 5, 19, 28, 46, 12, 7, 22, 25, 99, 36, 92] s = ct.heapsort() print ct>>> [1, 2, 5, 7, 12, 17, 19, 22, 25, 28, 36, 46, 92, 99] |
希望本文所述對大家Python程序設計有所幫助。
原文鏈接：http://www.cnblogs.com/hanahimi/p/4692668.html
