用代码解释堆
时间: 2023-09-20 10:12:10 浏览: 34
下面是用 Python 代码实现一个小根堆的例子,实现了堆的插入和弹出操作:
```python
class Heap:
def __init__(self):
self.heap = []
def push(self, val):
self.heap.append(val)
idx = len(self.heap) - 1
while idx > 0:
parent_idx = (idx - 1) // 2
if self.heap[parent_idx] > self.heap[idx]:
self.heap[parent_idx], self.heap[idx] = self.heap[idx], self.heap[parent_idx]
idx = parent_idx
else:
break
def pop(self):
if len(self.heap) == 0:
return None
if len(self.heap) == 1:
return self.heap.pop()
root = self.heap[0]
self.heap[0] = self.heap.pop()
idx = 0
while idx < len(self.heap):
left_idx = idx * 2 + 1
right_idx = idx * 2 + 2
min_idx = idx
if left_idx < len(self.heap) and self.heap[left_idx] < self.heap[min_idx]:
min_idx = left_idx
if right_idx < len(self.heap) and self.heap[right_idx] < self.heap[min_idx]:
min_idx = right_idx
if min_idx != idx:
self.heap[min_idx], self.heap[idx] = self.heap[idx], self.heap[min_idx]
idx = min_idx
else:
break
return root
```
这里使用列表来表示堆,插入时将元素添加到列表尾部,然后将元素与其父节点进行比较,如果父节点较大则交换两个节点,直到满足小根堆的性质。
弹出时将堆顶元素取出,将列表最后一个元素放到堆顶,然后将堆顶元素与其左右子节点中较小的那个进行比较,如果子节点较小则交换两个节点,直到满足小根堆的性质。
相关推荐
![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)