堆的python實現

class Heap(object):"""大頂堆的定義，實現插入和刪除"""def __init__(self, capacity):self.a = [None] * (capacity + 1)self.n = capacityself.count = 0def insert(self, data):"""插入一個數據"""if self.count >= self.n:return Falseself.count += 1i = self.countself.a[i] = data# 讓新插入的節點與父節點對比大小。如果不滿足子節點小于等于父節點的大小關系，# 我們就互換兩個節點。一直重復這個過程，直到所有的子節點小于等于父節點。while int(i / 2) > 0 and self.a[i] > self.a[int(i / 2)]:temp = self.a[i]self.a[i] = self.a[int(i / 2)]self.a[int(i / 2)] = tempi = int(i / 2)print(self.a)return Truedef remove_max(self):"""刪除大頂堆最大值"""if self.count == 0:return Falseself.a[1] = self.a[self.count]self.count -= 1self.heapify()print(self.a)return Truedef heapify(self):# 刪除堆頂元素之后，就需要把第二大的元素放到堆頂，那第二大元素肯定會出現在左右子節點中。# 然后我們再迭代地刪除第二大節點，以此類推，直到葉子節點被刪除。i = 1while True:max_pos = iif 2 * i <= self.count and self.a[i] < self.a[2 * i]:max_pos = 2 * iif 2 * i + 1 <= self.count and self.a[max_pos] < self.a[2 * i + 1]:max_pos = 2 * i + 1if max_pos == i:self.a[self.count + 1] = Nonebreaktemp = self.a[i]self.a[i] = self.a[max_pos]self.a[max_pos] = tempi = max_posdef build_heap(self, arr):"""算法從第1個下標開始計算，所以需要插入站位None"""n = len(arr)arr.insert(0, None)# 我們只對 n/2 開始到 1的數據進行堆化，下標是n/2+ 1 到 n 的節點都是葉子節點，不需要堆化，# 對于完全二叉樹來說，下標是n/2+ 1 到 n 的節點都是葉子節點for i in range(int(n / 2), 0, -1):self.heapify_by_arr(arr, n, i)return arr@staticmethoddef heapify_by_arr(arr, l, i):while True:max_pos = iif 2 * i <= l and arr[i] < arr[2 * i]:max_pos = 2 * iif 2 * i + 1 <= l and arr[max_pos] < arr[2 * i + 1]:max_pos = 2 * i + 1if max_pos == i:breaktemp = arr[i]arr[i] = arr[max_pos]arr[max_pos] = tempi = max_posdef sort_by_heap(self, arr):"""利用堆進行數組排序"""k = len(arr)arr = self.build_heap(arr)while k > 1:temp = arr[k]arr[k] = arr[1]arr[1] = tempk -= 1self.heapify_by_arr(arr, k, 1)print(arr)

總結

以上是生活随笔為你收集整理的大顶堆的python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。