25386147 构建个大顶堆
时间: 2023-07-30 16:11:43 浏览: 49
构建大顶堆的步骤如下:
1. 从最后一个非叶子节点开始,依次向上调整每个节点,使其满足大顶堆的性质。最后一个非叶子节点的索引为 n/2-1,其中 n 是堆的大小。
2. 对于每个非叶子节点 i,比较其与左右子节点的大小,将最大的值作为父节点,并将该值与子节点交换位置。如果发生了交换,则需要递归调整子节点的位置,直到满足大顶堆的性质。
下面是一个示例代码来构建一个大顶堆:
```python
def heapify(arr, n, i):
# 找到左右子节点的索引
left = 2 * i + 1
right = 2 * i + 2
largest = i
# 找到最大值
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大值不是父节点,则交换位置,并递归调整子节点的位置
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def build_heap(arr):
n = len(arr)
# 从最后一个非叶子节点开始,依次向上调整每个节点
for i in range(n//2-1, -1, -1):
heapify(arr, n, i)
return arr
```
你可以使用以下代码来测试:
```python
arr = [4, 10, 3, 5, 1]
print(build_heap(arr)) # 输出 [10, 5, 3, 4, 1]
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)