试用已知的n个整数先建立一个小顶堆。 共有m 次操作,每次 push 操作需要向堆内插入一个新整数,每次 pop操作则需要将堆顶元素弹出堆,并输出这个元素的值。
时间: 2024-03-06 22:47:32 浏览: 84
依次去掉n中的某一位数字,得到m个整数,并将这m个整数按从小到大的次序排列后输出.docx
5星 · 资源好评率100%
好的,这是一个经典的堆操作问题。我们可以使用数组来实现小顶堆,其中假设数组的下标从1开始,那么对于第i个位置上的元素,其左儿子为2i,右儿子为2i+1,父节点为i/2。
下面是一个基于数组实现的小顶堆的代码示例:
```python
class MinHeap:
def __init__(self, nums):
self.heap = [0] + nums
self.size = len(nums)
self.build_heap()
def build_heap(self):
for i in range(self.size // 2, 0, -1):
self.heapify_down(i)
def heapify_down(self, i):
while i * 2 <= self.size:
min_child = self.min_child(i)
if self.heap[i] > self.heap[min_child]:
self.heap[i], self.heap[min_child] = self.heap[min_child], self.heap[i]
i = min_child
def min_child(self, i):
if i * 2 + 1 > self.size:
return i * 2
else:
if self.heap[i * 2] < self.heap[i * 2 + 1]:
return i * 2
else:
return i * 2 + 1
def push(self, x):
self.heap.append(x)
self.size += 1
self.heapify_up(self.size)
def heapify_up(self, i):
while i // 2 > 0:
if self.heap[i] < self.heap[i // 2]:
self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]
i //= 2
def pop(self):
if self.size == 0:
return None
else:
min_val = self.heap[1]
self.heap[1] = self.heap[self.size]
self.size -= 1
self.heap.pop()
self.heapify_down(1)
return min_val
```
以上代码中,MinHeap类的构造函数接受一个数组nums,用于初始化小顶堆。build_heap()方法用于构建堆,heapify_down()方法用于从上往下维护堆的性质,heapify_up()方法用于从下往上维护堆的性质。push()方法用于向堆中插入一个新的元素,pop()方法用于弹出堆顶元素。
阅读全文