最大堆python代码
时间: 2023-10-12 22:55:27 浏览: 40
以下是一个用Python实现的最大堆的示例代码:
```python
class Max:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def insert(self, item):
self.heap.append(item)
i = len(self.heap) - 1
while i != 0 and self.heap[i] > self.heap[self.parent(i)]:
self.swap(i, self.parent(i))
i = self.parent(i)
def extract_max(self):
if len(self.heap) == 0:
return None
max_value = self.heap[0]
self.swap(0, len(self.heap) - 1)
self.heap.pop()
self.max_heapify(0)
return max_value
def max_heapify(self, i):
left = self.left_child(i)
right = self.right_child(i)
largest = i
if left < len(self.heap) and self.heap[left] > self.heap[largest]:
largest = left
if right < len(self.heap) and self.heap[right] > self.heap[largest]:
largest = right
if largest != i:
self.swap(i, largest)
self.max_heapify(largest)
```
这个代码定义了一个`MaxHeap`类,其中包含了最大堆的常用操作,如插入元素和提取最大值。你可以使用该类来创建一个最大堆对象,并对其进行操作。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)