Why T?
  • 板块灌水区
  • 楼主Wrong_Accept
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/6/22 19:32
  • 上次更新2024/6/22 20:31:18
查看原帖
Why T?
977599
Wrong_Accept楼主2024/6/22 19:32

我是用的堆啊,怎么 T 了呢?求大佬帮忙!谢谢。

提交记录在此!

代码(我用的 Python):

class MinHeap:
    def __init__(self):
        self.heap = list()

    def size(self):
        return len(self.heap)

    def empty(self):
        return not len(self.heap)

    def top(self):
        return self.heap[0] if len(self.heap) else None

    def push(self, key):
        self.heap.append(key)
        index = len(self.heap) - 1
        while index > 0 and self.heap[index] < self.heap[(index - 1) // 2]:
            self.heap[index], self.heap[(index - 1) // 2] = self.heap[(index - 1) // 2], self.heap[index]
            index = (index - 1) // 2

    def pop(self):
        if not len(self.heap):
            raise IndexError('pop from empty heap')
        if len(self.heap) == 1:
            return self.heap.pop()
        min_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        index = 0
        while True:
            smallest = index
            left = index * 2 + 1
            right = index * 2 + 2
            if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
                smallest = right
            if smallest == index:
                break
            else:
                self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
                index = smallest
        return min_value

min_heap = MinHeap()
times = int(input())
for ordinal in range(times):
    iter_ = map(int, input().split())
    op = next(iter_)
    if op == 1:
        min_heap.push(next(iter_))
    elif op == 2:
        print(min_heap.top())
    else:
        min_heap.pop()
2024/6/22 19:32
加载中...