用python写一个大根堆
时间: 2024-05-29 07:06:06 浏览: 157
以向下调整的方式建立大根堆
大根堆是一种特殊的二叉堆,它满足以下两个性质:
1. 父节点的值大于或等于其子节点的值。
2. 树中任意节点的值都大于或等于其子树中的所有节点的值。
在Python中,可以使用内置的heapq模块来实现大根堆。下面是一个用Python实现大根堆的示例代码:
```python
import heapq
class MaxHeap:
def __init__(self):
self.heap = []
def push(self, item):
heapq.heappush(self.heap, -item)
def pop(self):
return -heapq.heappop(self.heap)
def peek(self):
return -self.heap
def size(self):
return len(self.heap)
# 示例用法
heap = MaxHeap()
heap.push(5)
heap.push(3)
heap.push(8)
print(heap.pop()) # 输出:8
print(heap.peek()) # 输出:5
print(heap.size()) # 输出:2
```
上述代码中,我们定义了一个`MaxHeap`类,其中使用了`heapq`模块提供的函数来实现大根堆的功能。`push`方法用于向堆中插入元素,`pop`方法用于弹出堆顶元素,`peek`方法用于获取堆顶元素但不弹出,`size`方法用于获取堆的大小。
阅读全文