我是用的堆啊,怎么 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()