堆是一種特殊的樹形結構， 堆中的數據存儲滿足一定的堆序。堆排序是一種選擇排序， 其算法復雜度， 時間復雜度相對于其他的排序算法都有很大的優勢。
堆分為大頭堆和小頭堆， 正如其名， 大頭堆的第一個元素是最大的， 每個有子結點的父結點， 其數據值都比其子結點的值要大。小頭堆則相反。
我大概講解下建一個樹形堆的算法過程:
找到N/2 位置的數組數據， 從這個位置開始， 找到該節點的左子結點的索引， 先比較這個結點的下的子結點， 找到最大的那個， 將最大的子結點的索引賦值給左子結點， 然后將最大的子結點和父結點進行對比， 如果比父結點大， 與父節點交換數據。當然， 我只是大概說了下實現， 在此過程中， 還需要考慮結點不存在的情況。
看下代碼：
# 構建二叉堆 def binaryHeap(arr, lenth, m): temp = arr[m] # 當前結點的值 while(2*m+1 < lenth): lchild = 2*m+1 if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]: lchild = lchild + 1 if temp < arr[lchild]: arr[m] = arr[lchild] else: break m = lchild arr[m] = temp def heapsort(arr, length): i = int(len(arr)/2) while(i >= 0): binaryHeap(arr, len(arr), i) i = i - 1 print("二叉堆的物理順序為:") print(arr) # 輸出二叉堆的物理順序 if __name__ == '__main__': arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98] heapsort(arr, len(arr))堆排序過程就是依次將最后的結點與首個節點進行對比交換：
# 構建二叉堆def binaryHeap(arr, lenth, m): temp = arr[m] # 當前結點的值 while(2*m+1 < lenth): lchild = 2*m+1 if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]: lchild = lchild + 1 if temp < arr[lchild]: arr[m] = arr[lchild] else: break m = lchild arr[m] = tempdef heapsort(arr, length): i = int(len(arr)/2) while(i >= 0): binaryHeap(arr, len(arr), i) i = i - 1 print("二叉堆的物理順序為:") print(arr) # 輸出二叉堆的物理順序 i = length-1 while(i > 0): arr[i], arr[0] = arr[0], arr[i] # 變量交換 binaryHeap(arr, i, 0) i = i - 1560def pop(arr): first = arr.pop(0) return firstif __name__ == '__main__': arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98] heapsort(arr, len(arr)) print("堆排序后的物理順序") print(arr) # 輸出經過堆排序之后的物理順序 data = pop(arr) print(data) print(arr)python封裝了一個堆模塊, 我們使用該模塊可以很高效的實現一個優先隊列
import heapqclass Item: def __init__(self, name): self.name = name def __repr__(self): return 'Item({!r})'.format(self.name)class PriorityQueue: def __init__(self): self._queue = [] self._index = 0 def push(self, item, priority): heapq.heappush(self._queue, (-priority, self._index, item)) # 存入一個三元組 self._index += 1 def pop(self): return heapq.heappop(self._queue)[-1] # 逆序輸出if __name__ == '__main__': p = PriorityQueue() p.push(Item('foo'), 1) p.push(Item('bar'), 5) p.push(Item('spam'), 4) p.push(Item('grok'), 1) print(p.pop()) print(p.pop())具體請看heapq官網
以上這篇python下實現二叉堆以及堆排序的示例就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持VEVB武林網。
新聞熱點
疑難解答
