在 Python 中獲取最大堆

Jesse John 2023年1月30日 2022年7月18日
  1. 在 Python 中使用數字獲取最大堆
  2. 在 Python 中使用元組獲取最大堆
  3. 參考
在 Python 中獲取最大堆

堆是實現優先順序佇列的首選資料結構。與二叉搜尋樹不同,堆不是完全有序的;兄弟姐妹或堂兄弟之間沒有明確的順序。

在 Python 中,heapq 模組實現了堆佇列演算法。然而,heapq 僅提供 Min Heap 實現,其中任何父節點的值小於或等於其子節點的值。

主函式 heappop() 返回堆的最小元素。

本文將討論通過將 heapq 與一些自定義程式碼結合來在 Python 中實現最大堆行為。

在 Python 中使用數字獲取最大堆

處理數字時最常見的策略是將列表的元素乘以 -1。heapq 函式可以處理堆。

彈出最小值後,我們需要再次將輸出乘以 -1 以獲得最大值。

示例程式碼:

# import the heapq module.
import heapq

# Max Heap With Numbers

# Create a list.
x = [5, 4, 3, 6, 8, 7, 2, 1]
# Print the list.
print(x)

# Multiply elements by -1.
x_inv = [-1*i for i in x]
print(x_inv)

# Make the heap.
heapq.heapify(x_inv)

# Pop the maximum value.
# RUN ONE LINE AT A TIME.
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)

輸出:

print(x)
[5, 4, 3, 6, 8, 7, 2, 1]

print(x_inv)
[-5, -4, -3, -6, -8, -7, -2, -1]

-1 * heapq.heappop(x_inv)
Out[8]: 8

-1 * heapq.heappop(x_inv)
Out[9]: 7

-1 * heapq.heappop(x_inv)
Out[10]: 6

在 Python 中使用元組獲取最大堆

我們可能想用元組而不是數字來實現一個優先順序佇列。由於 Python 的元組是不可變的,這對將優先順序數乘以 -1 的任務是一個挑戰。

解決方案在於首先將每個元組轉換為列表,將這些子列表的第一個元素修改為 -1,將它們轉換回元組,同時使用這些元組建立一個新列表。然後使用 heapify() 將新列表轉換為堆。

要彈出最大值,我們在堆上使用 heappop(),將元組轉換為列表,修改第一個元素以獲得正值,然後將列表轉換回元組。

示例程式碼:

# Max Heap With Tuples

# Make a list of tuples.
l = [(1, "A"), (5, "B"), (3, "C"), (7, "D"), (6.5, "E")]
# View the list.
l

# Create an empty list to hold modified tuples.
l_max = []

# Populate the list with modified tuples.
for i in range(len(l)):
    j = list(l[i])
    j[0] = -1* j[0]
    l_max.append(tuple(j))

# View the modified list.
l_max

# Create the min heap.
heapq.heapify(l_max)

# View the min-heap.
l_max

# Create a function that uses meappop and
# changes the number back to a positive value.
def maxpop(mh):
    l = list(heapq.heappop(mh))
    l[0] = -1*l[0]
    return tuple(l)

# Test the values popped by the maxpop.
# RUN ONE LINE AT A TIME.
maxpop(l_max)
maxpop(l_max)
maxpop(l_max)

輸出:

l
Out[15]: [(1, 'A'), (5, 'B'), (3, 'C'), (7, 'D'), (6.5, 'E')]

l_max
Out[14]: [(-1, 'A'), (-5, 'B'), (-3, 'C'), (-7, 'D'), (-6.5, 'E')]

heapq.heapify(l_max)

l_max
Out[17]: [(-7, 'D'), (-6.5, 'E'), (-3, 'C'), (-5, 'B'), (-1, 'A')]

maxpop(l_max)
Out[19]: (7, 'D')

maxpop(l_max)
Out[20]: (6.5, 'E')

maxpop(l_max)
Out[21]: (5, 'B')

其他需要的堆函式可以使用相同的技術來實現。

參考

參見 Python 的 heapq 模組 的文件以瞭解更多細節和例子。

Python 開發團隊決定不實現最大堆函式。你可以在此處閱讀功能請求和響應。

Author: Jesse John
Jesse John avatar Jesse John avatar

Jesse is passionate about data analysis and visualization. He uses the R statistical programming language for all aspects of his work.