最大、小堆積樹
最大堆積樹（Max Heap）和小堆積樹（Min Heap）是兩種特殊的二元樹結構，主要用於實現優先佇列。
介紹
最大堆積樹（Max Heap）
- 定義：在最大堆積樹中，每個節點的值都大於或等於其子節點的值。
- 特性：
- 根節點（root）的值是整個堆積樹中的最大值。
- 對於任意節點
i，其子節點2*i和2*i + 1的值都小於或等於節點i的值。
- 應用：最大堆積樹常用於實現優先佇列，特別是需要快速取出最大值的情況。
小堆積樹（Min Heap）
- 定義：在小堆積樹中，每個節點的值都小於或等於其子節點的值。
- 特性：
- 根節點（root）的值是整個堆積樹中的最小值。
- 對於任意節點
i，其子節點2*i和2*i + 1的值都大於或等於節點i的值。
- 應用：小堆積樹常用於實現優先佇列，特別是需要快速取出最小值的情況。
範例程式碼
以下是判斷一個樹是否為最大堆積樹或小堆積樹的 Python 範例：
python
def isMinStackTree():
for i in range(1, len(tree) - 5):
if tree[i] > tree[i*2] or tree[i] > tree[i * 2 + 1]:
return False
return True
def isMaxStackTree():
for i in range(1, len(tree) - 5):
if tree[i] < tree[i*2] or tree[i] < tree[i * 2 + 1]:
return False
return True
for _ in range(int(input())):
tree = [0] + list(map(int, input().split(',')))
if isMinStackTree() or isMaxStackTree():
print('T')
else:
print("F")說明
isMinStackTree函數：檢查樹是否為小堆積樹。如果任意節點的值大於其子節點的值，則返回FalseisMaxStackTree函數：檢查樹是否為最大堆積樹。如果任意節點的值小於其子節點的值，則返回False- 主程式：讀取輸入的樹，並檢查其是否為最大堆積樹或小堆積樹，然後輸出結果。
這些堆積樹結構在許多演算法和數據結構中都有廣泛的應用，特別是在需要高效優先級操作的情況下。
是否為堆積樹 105 模擬試題 5
python
def isMinStackTree():
for i in range(1, len(tree) - 5):
# print(tree[i], tree[i * 2], tree[i * 2 + 1])
if tree[i] > tree[i*2] or tree[i] > tree[i * 2 + 1]:
return False
return True
def isMaxStackTree():
for i in range(1, len(tree) - 5):
# print(tree[i], tree[i * 2], tree[i * 2 + 1])
if tree[i] < tree[i*2] or tree[i] < tree[i * 2 + 1]:
return False
return True
for _ in range(int(input())):
tree = [0] + list(map(int, input().split(',')))
if isMinStackTree() or isMaxStackTree():
print('T')
else:
print("F")例題
E2 數字迷宮 V2 解法:跑BFS,堆積,優先佇列
python
import heapq
def bfs():
queue = [(maze[0][0], 0, 0)]
visited = [[0 for _ in range(w)] for _ in range(h)]
while queue:
cost, i, j = heapq.heappop(queue)
if visited[i][j]:
continue
visited[i][j] = 1
if i == h - 1 and j == w - 1:
return cost
for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
x = i + dx
y = j + dy
if (0 <= x < h) and (0 <= y < w) and (not visited[x][y]):
heapq.heappush(queue, (cost + maze[x][y], x, y))
for _ in range(int(input())):
h = int(input())
w = int(input())
maze = [list(map(int, input().split())) for _ in range(h)]
print(bfs())E 是否為堆積樹 或二元搜尋樹
python
def min_heap():
for i in range(1, n):
if i * 2 < n:
if tree[i * 2] > tree[i]:
return False
if i * 2 + 1 < n:
if tree[i * 2 + 1] > tree[i]:
return False
return True
def max_heap():
for i in range(1, n):
if i * 2 < n:
if tree[i * 2] < tree[i]:
return False
if i * 2 + 1 < n:
if tree[i * 2 + 1] < tree[i]:
return False
return True
def binary():
for i in range(1, n):
if i * 2 < n:
if tree[i * 2] > tree[i]:
return False
if i * 2 + 1 < n:
if tree[i * 2 + 1] < tree[i]:
return False
return True
for _ in range(int(input())):
tree = [0] + list(map(int, input().split(',')))
n = len(tree)
if min_heap() or max_heap():
print('H')
elif binary():
print('B')
else:
print('F')Contributors
lucashsu95