为何Python最小堆未返回最小值？代码问题求助

核心问题 #

• 直接调用list.remove()修改堆结构会破坏heapq的堆性质，导致后续heappop无法正确返回堆顶元素。
• heapq模块仅通过heappush和heappop维护堆的完全二叉树结构，手动修改列表（如remove、del）后，堆的顺序不会自动调整，堆的有效性彻底丧失。

问题分析 #

以你最后一次调用highestRated的场景为例：
执行完两次changeRating后，堆中同时存在旧的无效记录(-15, "kbaxapl")和新记录(-8, "kbaxapl")，还有(-12, "czopaaeyl")、(-5, "lxoozsbh")。但之前调用self.hashset[c].remove((-r, food))后，没有重新触发堆化操作，堆的结构已经混乱，堆顶仍是旧的无效记录(-15, "kbaxapl")。你的代码直接将其弹出再放回，导致返回了错误的食物名称。

修复方案 #

采用惰性删除策略：不再手动删除堆中的旧记录，而是在每次获取堆顶时，检查该记录是否与食物的最新评分一致，不一致则弹出无效记录，直到找到有效堆顶。

修复后的代码：

from collections import defaultdict
import heapq
from typing import List

class FoodRatings:

    def __init__(self, foods: List[str], cuisines: List[str], ratings: List[int]):
        self.food_info = {}  # 存储每个食物的(菜系, 最新评分)
        self.cuisine_heap = defaultdict(list)  # 每个菜系对应的最大堆（用负评分实现）
        
        for f, c, r in zip(foods, cuisines, ratings):
            self.food_info[f] = (c, r)
            heapq.heappush(self.cuisine_heap[c], (-r, f))    
  
    def changeRating(self, food: str, newRating: int) -> None:
        c, _ = self.food_info[food]
        # 直接推入新评分记录，旧记录留在堆中后续惰性删除
        heapq.heappush(self.cuisine_heap[c], (-newRating, food))
        self.food_info[food] = (c, newRating)

    def highestRated(self, cuisine: str) -> str:
        heap = self.cuisine_heap[cuisine]
        # 过滤无效旧记录：堆顶评分与食物最新评分不一致则弹出
        while heap:
            current_neg_r, food = heap[0]
            current_r = -current_neg_r
            _, latest_r = self.food_info[food]
            if current_r == latest_r:
                return food
            heapq.heappop(heap)
        return ""

修复逻辑说明 #

1. 移除remove操作：避免手动修改堆结构，直接向堆中推入新的评分记录，旧记录暂时保留。
2. 堆顶有效性检查：每次调用highestRated时，循环检查堆顶元素的评分是否与food_info中存储的最新评分一致。若不一致，说明该记录是旧的无效数据，直接弹出；直到找到有效堆顶后返回对应的食物名称。

验证结果 #

最后一次调用highestRated时，堆中旧的(-15, "kbaxapl")会被检测为无效并弹出，后续堆顶变为(-12, "czopaaeyl")，其评分与food_info中的最新评分一致，因此返回"czopaaeyl"，符合预期输出。

内容的提问来源于stack exchange，提问作者Maverick