heap python_数据结构-堆(Heap) Python实现
堆(Heap)可以看成近似完全二叉樹的數組，樹中每個節點對應數組中一個元素。除了最底層之外，該樹是完全充滿的，最底層是從左到右填充的。
堆包括最大堆和最小堆：最大堆的每一個節點(除了根結點)的值不大于其父節點；最小堆的每一個節點(除了根結點)的值不小于其父節點。
本文以最大堆為例，先直觀感受一下堆的樣子：
圖片來源
最大堆
樹中節點內的值表示存儲的值，節點旁邊的值表示該節點在數組中的下標。
觀察上圖不難發現，對于一個給定節點的下標i，其父節點、左孩子、右孩子的下標為：
parent(i): (i + 1) // 2 - 1
left(i): i * 2 + 1
right(i): i * 2 + 2
其中“//”表示除法后只取整數部分。
對于一個給定的數組，如何轉化為堆呢？
對于一個任意節點，如果該節點大于左孩子和右孩子，則該節點無需移動。否則，和左右孩子中較大的那個交換位置，于是該節點滿足大于左右孩子了，但是剛被交換了的孩子節點需要繼續比較它的左右孩子......整個過程遞歸進行下去，我們可以輕松計算出：對于根節點，在進行轉化成堆的過程中，最多需要交換h次(h為樹的高度)，對于樹種的每個節點，如果都進行此操作，則整個過程的時間復雜度為：O(nlogn)。(n為節點數，logn≈h)
代碼如下：
def heapify(self):
for i in range((len(self.heap) + 1) // 2 - 1, -1, -1):
self.max_heapify_top(i)
def max_heapify_top(self, i):
"""
從上到下
O(logn)
"""
left = i * 2 + 1
right = i * 2 + 2
if left < len(self.heap) and self.heap[left] > self.heap[i]:
largest = left
else:
largest = i
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.heap[largest], self.heap[i] = self.heap[i], self.heap[largest]
self.max_heapify_top(largest)
以上代碼中heapify函數從(len(self.heap) + 1) // 2 - 1到0進行遍歷，是因為樹中的葉子節點沒有孩子，因此可以看成滿足堆的性質，所以無需進行heapify，所以從非葉子節點開始遍歷，節約時間。
如何從堆中彈出和插入元素呢？
先說彈出。由于是最大堆，因此每次彈出需要彈出最大的元素，那就是根節點，如何彈出后還保持堆的性質呢。具體做法是：先將樹中根節點和最后一個節點交換位置，對應數組中就是第一個元素和最后一個元素交換位置，然后彈出最后一個元素，在對交換位置后的根節點進行heapify，這樣彈出了最大元素，同時也保持了堆的性質。
代碼如下：
def pop(self):
"""
O(logn)
"""
self.heap[0], self.heap[len(self.heap) - 1] = self.heap[len(self.heap) - 1], self.heap[0]
value = self.heap.pop()
self.max_heapify_top(0)
return value
插入元素。
先將元素放在樹的末尾，也是數組的末尾，再按照自下而上的順序依次比較與父節點的大小關系，自下而上進行heapify。
代碼如下：
def push(self, value):
"""
O(logn)
"""
self.heap.append(value)
self.max_heapify_button(len(self.heap) - 1)
def max_heapify_button(self, i):
"""
從下到上
O(logn)
"""
parent = (i + 1) // 2 - 1
if parent >= 0 and self.heap[parent] < self.heap[i]:
smallest = parent
else:
smallest = i
if smallest != i:
self.heap[smallest], self.heap[i] = self.heap[i], self.heap[smallest]
self.max_heapify_button(smallest)
整個堆的實現代碼為：
class Heap:
def __init__(self, heap=[]):
self.heap = heap
def heapify(self):
for i in range((len(self.heap) + 1) // 2 - 1, -1, -1):
self.max_heapify_top(i)
def max_heapify_top(self, i):
"""
從上到下
O(logn)
"""
left = i * 2 + 1
right = i * 2 + 2
if left < len(self.heap) and self.heap[left] > self.heap[i]:
largest = left
else:
largest = i
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.heap[largest], self.heap[i] = self.heap[i], self.heap[largest]
self.max_heapify_top(largest)
def max_heapify_button(self, i):
"""
從下到上
O(logn)
"""
parent = (i + 1) // 2 - 1
if parent >= 0 and self.heap[parent] < self.heap[i]:
smallest = parent
else:
smallest = i
if smallest != i:
self.heap[smallest], self.heap[i] = self.heap[i], self.heap[smallest]
self.max_heapify_button(smallest)
def pop(self):
"""
O(logn)
"""
self.heap[0], self.heap[len(self.heap) - 1] = self.heap[len(self.heap) - 1], self.heap[0]
value = self.heap.pop()
self.max_heapify_top(0)
return value
def push(self, value):
"""
O(logn)
"""
self.heap.append(value)
self.max_heapify_button(len(self.heap) - 1)
再說堆排序呢？對于一個任意的數組，進行構建堆之后，再按照順序依次彈出堆中的元素，便得到了有序的數組。更神奇的是，在數組末尾添加一個指針，便可實現數組的原地排序(不需要額外空間)。堆排序的時間復雜度為：O(nlogn)，空間復雜度為：O(1)
總結
以上是生活随笔為你收集整理的heap python_数据结构-堆(Heap) Python实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java小结（一）——打印等腰三角形
- 下一篇： Java小结（二）——打印矩形和九九乘法