基于最大堆的优先队列Python实现异常求助：输出值错误

问题背景 #

学校作业需求：阿姆斯特丹市需存储历年新冠检测数据，通过最大堆实现优先队列以快速获取新冠等级的最大值，返回对应日期与等级。

• 输入格式：yyyy-mm-dd, 传感器ID, 新冠等级，多组数据用;分隔
• 示例输入：2022−09−08, 23, 371; 2022−09−08, 2, 3171; 2022−09−08, 12, 43; 2021−03−21, 4, 129
• 预期输出：2022−09−08, 3171
• 实际异常输出：('1.1.1977', 9223372036854775807)

代码缺陷分析 #

1. 堆哨兵元素设计错误 #

初始化时设置的哨兵self.Heap[0] = ('1.1.1977', sys.maxsize)会触发插入逻辑的错误交换：
Python中元组比较按元素顺序逐个进行，插入的(日期, 等级)元组中，日期字符串（如'2022-09-08'）首字符'2'大于哨兵日期的首字符'1'，因此整个元组会被判定为大于哨兵。插入时用户元素会与哨兵交换位置，导致堆的FRONT（位置1）变成哨兵元素，最终extractMax()返回的是哨兵而非真实数据。

2. 堆排序的优先级逻辑错误 #

当前插入的元组是(日期, 等级)，堆的比较会优先基于日期字符串，而非需求中的新冠等级。这会导致日期新但等级小的元素被误判为更大值，不符合作业要求。

3. 输入处理未清理空格 #

输入分割后，新冠等级字符串可能带有前置空格（如' 371'），虽然Python的int()可以自动处理，但存在潜在格式风险。

修复后的代码 #

import sys

class MaxHeap:
    def __init__(self, maxsize):
        self.maxsize = maxsize
        self.size = 0
        self.Heap = [0] * (self.maxsize + 1)
        # 哨兵设置为最小优先级（等级为-∞，日期不影响）
        self.Heap[0] = (-sys.maxsize, '')
        self.FRONT = 1

    def parent(self, pos):
        return pos // 2

    def leftChild(self, pos):
        return 2 * pos

    def rightChild(self, pos):
        return (2 * pos) + 1

    def isLeaf(self, pos):
        return pos >= (self.size // 2) and pos <= self.size

    def swap(self, fpos, spos):
        self.Heap[fpos], self.Heap[spos] = self.Heap[spos], self.Heap[fpos]

    def maxHeapify(self, pos):
        if not self.isLeaf(pos):
            left = self.leftChild(pos)
            right = self.rightChild(pos)
            # 优先比较新冠等级（元组第一个元素）
            if (self.Heap[pos][0] < self.Heap[left][0] or
                self.Heap[pos][0] < self.Heap[right][0]):
                if self.Heap[left][0] > self.Heap[right][0]:
                    self.swap(pos, left)
                    self.maxHeapify(left)
                else:
                    self.swap(pos, right)
                    self.maxHeapify(right)

    def insert(self, element):
        if self.size >= self.maxsize:
            return
        self.size += 1
        self.Heap[self.size] = element
        current = self.size
        # 基于新冠等级（元组第一个元素）比较
        while self.Heap[current][0] > self.Heap[self.parent(current)][0]:
            self.swap(current, self.parent(current))
            current = self.parent(current)

    def extractMax(self):
        if self.size == 0:
            return None
        extraction = self.Heap[self.FRONT]
        self.Heap[self.FRONT] = self.Heap[self.size]
        self.size -= 1
        self.maxHeapify(self.FRONT)
        # 返回时转换为（日期，等级）的格式
        return (extraction[1], extraction[0])

if __name__ == "__main__":
    input_str = input()
    data_groups = input_str.split(";")
    heap_data = []
    for group in data_groups:
        # 清理前后空格，再分割
        parts = group.strip().split(',', 2)
        date = parts[0].strip()
        # 提取新冠等级并转换为整数
        level = int(parts[2].strip())
        # 存储为（等级，日期），确保堆按等级排序
        heap_data.append((level, date))

    heap = MaxHeap(len(heap_data))
    for item in heap_data:
        heap.insert(item)

    # 获取结果并按要求格式输出
    result = heap.extractMax()
    print(f"{result[0]}, {result[1]}")

修复说明 #

1. 修正哨兵元素：将哨兵设置为(-sys.maxsize, '')，确保任何真实数据的等级都大于哨兵，避免插入时的错误交换。
2. 调整元组顺序：将插入堆的元组改为(新冠等级, 日期)，让堆的比较逻辑基于等级大小，符合需求。
3. 优化输入处理：添加strip()清理字符串前后空格，避免格式异常。
4. 明确比较逻辑：在maxHeapify和insert方法中，明确基于元组第一个元素（等级）进行比较，避免歧义。

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