贪心算法与优先队列实战解析

贪心算法与优先队列详解

1. 贪心算法核心思想

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的算法策略。其核心特征如下：

贪心算法的基本设计步骤：

2. 优先队列概念与实现

优先队列（Priority Queue）是一种特殊的队列，其中每个元素都有相关的优先级，出队顺序由优先级决定而非入队顺序。

Python中的优先队列实现

Python提供了heapq模块来实现最小堆，可以用于构建优先队列：

import heapq

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):
"""弹出优先级最高的元素"""
if self._queue:
return heapq.heappop(self._queue)[-1]
raise IndexError("优先队列为空")

def is_empty(self):
return len(self._queue) == 0

# 使用示例
pq = PriorityQueue()
pq.push('任务A', 3)
pq.push('任务B', 1)
pq.push('任务C', 2)

print(pq.pop()) # 输出：任务B（优先级最高）
print(pq.pop()) # 输出：任务C
print(pq.pop()) # 输出：任务A

3. 贪心算法经典应用案例

案例1：活动选择问题

def activity_selection(activities):
"""
活动选择问题：选择最多的互不冲突的活动
activities: [(start_time, end_time), …]
"""
# 按照结束时间排序 – 贪心选择
activities.sort(key=lambda x: x[1])

selected = []
last_end = 0

for start, end in activities:
if start >= last_end: # 活动不冲突
selected.append((start, end))
last_end = end

return selected

# 测试示例
activities = [(1, 3), (2, 5), (4, 7), (1, 8), (5, 9), (8, 10)]
result = activity_selection(activities)
print(f"最多可安排活动数量: {len(result)}")
print(f"具体安排: {result}")

案例2：哈夫曼编码

import heapq
from collections import Counter

class HuffmanNode:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None

def __lt__(self, other):
return self.freq < other.freq

def build_huffman_tree(text):
"""构建哈夫曼树"""
# 统计字符频率
freq_counter = Counter(text)

# 创建优先队列（最小堆）
priority_queue = []
for char, freq in freq_counter.items():
heapq.heappush(priority_queue, HuffmanNode(char, freq))

# 构建哈夫曼树
while len(priority_queue) > 1:
# 取出频率最小的两个节点
left = heapq.heappop(priority_queue)
right = heapq.heappop(priority_queue)

# 创建新节点
merged = HuffmanNode(None, left.freq + right.freq)
merged.left = left
merged.right = right

heapq.heappush(priority_queue, merged)

return heapq.heappop(priority_queue)

def generate_huffman_codes(node, current_code="", codes={}):
"""生成哈夫曼编码"""
if node is None:
return

if node.char is not None:
codes[node.char] = current_code

generate_huffman_codes(node.left, current_code + "0", codes)
generate_huffman_codes(node.right, current_code + "1", codes)

return codes

# 哈夫曼编码示例
text = "abracadabra"
huffman_tree = build_huffman_tree(text)
huffman_codes = generate_huffman_codes(huffman_tree)

print("哈夫曼编码表:")
for char, code in huffman_codes.items():
print(f"'{char}': {code}")

案例3：最短木板问题（结合贪心与优先队列）

import heapq

def shortest_board_optimization(boards, operations):
"""
最短木板优化问题
每次对最短的木板进行操作，使其长度+1
boards: 木板初始长度列表
operations: 可执行的操作次数
"""
# 使用最小堆实现优先队列
heapq.heapify(boards)

for _ in range(operations):
# 取出当前最短的木板
shortest = heapq.heappop(boards)
# 增加长度并重新放入堆中
heapq.heappush(boards, shortest + 1)

return boards[0] # 返回最终的最短木板长度

# 测试示例
boards = [2, 5, 3, 7, 1]
operations = 4
result = shortest_board_optimization(boards, operations)
print(f"优化后的最短木板长度: {result}")
print(f"所有木板长度: {sorted(boards)}")

4. 贪心算法的优势与局限性

优势分析

局限性

def greedy_coin_change(coins, amount):
"""贪心零钱兑换 – 可能不是最优解"""
coins.sort(reverse=True) # 从大到小排序
result = []

for coin in coins:
while amount >= coin:
result.append(coin)
amount -= coin

return result if amount == 0 else None

def dp_coin_change(coins, amount):
"""动态规划零钱兑换 – 保证最优解"""
dp = [float('inf')] * (amount + 1)
dp[0] = 0

for i in range(1, amount + 1):
for coin in coins:
if i >= coin:
dp[i] = min(dp[i], dp[i – coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

# 对比示例
coins = [1, 3, 4]
amount = 6

greedy_result = greedy_coin_change(coins, amount)
dp_result = dp_coin_change(coins, amount)

print(f"贪心算法结果: {greedy_result}, 硬币数量: {len(greedy_result)}")
print(f"动态规划结果: 最少需要 {dp_result} 枚硬币")

5. 实际应用场景总结

贪心算法与优先队列的结合在以下场景中特别有效：

贪心算法的关键在于证明其贪心选择性质，即局部最优解能导致全局最优解。在实际应用中，需要仔细分析问题特性，确定是否适合使用贪心策略。优先队列则提供了高效管理优先级数据结构的工具，两者结合能够解决许多复杂的优化问题。

参考来源

• 华为OD机试：如何使用贪心算法与优先队列解决最短木板长度问题（C++、Java、JavaScript、Python实现）
• 【贪心算法经典应用】哈夫曼编码原理与算法详解 python
• C++ 教程 | 一文掌握元组、匿名函数、比较函数与优先队列（含详细示例）
• Python应用算法之贪心算法理解和实践
• 贪心算法原理与Python实战详解
• Python算法详解：贪心算法