数据结构堆排序（数据结构堆排序输出堆顶元素）

## 数据结构堆排序### 简介堆排序（Heap Sort）是一种高效的比较排序算法，其时间复杂度在最坏情况下也能达到 O(n log n)。它利用了一种称为“堆”的数据结构来实现排序。堆是一种特殊的二叉树，满足以下性质：-

结构性质：

堆是一棵完全二叉树，除了最后一层，其他层的节点都是满的，最后一层的节点尽可能从左到右排列。 -

堆序性质：

堆中每个节点的值都大于等于（或小于等于）其子节点的值。如果父节点的值大于等于子节点的值，称为

最大堆

（max heap）；如果父节点的值小于等于子节点的值，称为

最小堆

（min heap）。堆排序的基本思想是：将待排序的数组构建成一个堆，然后依次取出堆顶元素（最大堆的堆顶元素是最大值，最小堆的堆顶元素是最小值），即可得到有序序列。### 堆排序步骤1.

构建初始堆:

将待排序的数组构建成一个最大堆（升序排序）或最小堆（降序排序）。 2.

取出堆顶元素:

将堆顶元素与堆的最后一个元素交换，然后将堆的大小减 1。 3.

调整堆:

将新的堆顶元素向下调整，使其满足堆序性质。 4.

重复步骤 2 和 3:

重复执行步骤 2 和 3，直到堆的大小为 1。### 详细说明#### 1. 构建初始堆构建初始堆可以使用自底向上的方法，从最后一个非叶子节点开始，依次向上调整每个节点，使其满足堆序性质。

代码示例（以最大堆为例）：

```python def heapify(arr, n, i):"""调整堆，使以 i 为根节点的子树满足堆序性质。Args:arr: 待调整的数组。n: 堆的大小。i: 待调整的节点索引。"""largest = i # 初始化最大值为根节点索引left = 2

i + 1 # 左子节点索引right = 2

i + 2 # 右子节点索引# 找到最大值的索引if left < n and arr[left] > arr[largest]:largest = leftif 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):"""构建初始堆。Args:arr: 待排序的数组。"""n = len(arr)# 从最后一个非叶子节点开始调整for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i) ```#### 2. 取出堆顶元素每次从堆顶取出元素后，都需要将堆的最后一个元素放到堆顶，然后将堆的大小减 1。#### 3. 调整堆将新的堆顶元素向下调整，使其满足堆序性质。调整的方法与构建初始堆时相同，都是使用 `heapify()` 函数。#### 4. 重复步骤 2 和 3重复执行步骤 2 和 3，直到堆的大小为 1，此时数组就已排好序。

代码示例（堆排序完整代码）：

```python def heap_sort(arr):"""堆排序。Args:arr: 待排序的数组。"""n = len(arr)# 构建初始堆build_heap(arr)# 循环取出堆顶元素for i in range(n - 1, 0, -1):# 将堆顶元素与最后一个元素交换arr[i], arr[0] = arr[0], arr[i]# 调整堆heapify(arr, i, 0) ```### 总结堆排序是一种高效的排序算法，其时间复杂度稳定在 O(n log n)。它利用堆这种数据结构，通过不断地取出堆顶元素并调整堆来实现排序。堆排序是一种原地排序算法，只需要常数级别的额外空间。### 优点

时间复杂度稳定：

堆排序的时间复杂度在最好、平均和最坏情况下都是 O(n log n)。

原地排序：

堆排序只需要常数级别的额外空间。### 缺点

不稳定排序：

堆排序可能会改变相等元素的相对顺序。

递归深度：

堆排序的 `heapify()` 函数是递归调用的，可能会导致递归深度过深。

数据结构堆排序

简介堆排序（Heap Sort）是一种高效的比较排序算法，其时间复杂度在最坏情况下也能达到 O(n log n)。它利用了一种称为“堆”的数据结构来实现排序。堆是一种特殊的二叉树，满足以下性质：- **结构性质：** 堆是一棵完全二叉树，除了最后一层，其他层的节点都是满的，最后一层的节点尽可能从左到右排列。 - **堆序性质：** 堆中每个节点的值都大于等于（或小于等于）其子节点的值。如果父节点的值大于等于子节点的值，称为**最大堆**（max heap）；如果父节点的值小于等于子节点的值，称为**最小堆**（min heap）。堆排序的基本思想是：将待排序的数组构建成一个堆，然后依次取出堆顶元素（最大堆的堆顶元素是最大值，最小堆的堆顶元素是最小值），即可得到有序序列。

堆排序步骤1. **构建初始堆:** 将待排序的数组构建成一个最大堆（升序排序）或最小堆（降序排序）。 2. **取出堆顶元素:** 将堆顶元素与堆的最后一个元素交换，然后将堆的大小减 1。 3. **调整堆:** 将新的堆顶元素向下调整，使其满足堆序性质。 4. **重复步骤 2 和 3:** 重复执行步骤 2 和 3，直到堆的大小为 1。

详细说明

1. 构建初始堆构建初始堆可以使用自底向上的方法，从最后一个非叶子节点开始，依次向上调整每个节点，使其满足堆序性质。**代码示例（以最大堆为例）：**```python def heapify(arr, n, i):"""调整堆，使以 i 为根节点的子树满足堆序性质。Args:arr: 待调整的数组。n: 堆的大小。i: 待调整的节点索引。"""largest = i

初始化最大值为根节点索引left = 2 * i + 1

左子节点索引right = 2 * i + 2

右子节点索引

找到最大值的索引if left < n and arr[left] > arr[largest]:largest = leftif 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):"""构建初始堆。Args:arr: 待排序的数组。"""n = len(arr)

从最后一个非叶子节点开始调整for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i) ```

2. 取出堆顶元素每次从堆顶取出元素后，都需要将堆的最后一个元素放到堆顶，然后将堆的大小减 1。

3. 调整堆将新的堆顶元素向下调整，使其满足堆序性质。调整的方法与构建初始堆时相同，都是使用 `heapify()` 函数。

4. 重复步骤 2 和 3重复执行步骤 2 和 3，直到堆的大小为 1，此时数组就已排好序。**代码示例（堆排序完整代码）：**```python def heap_sort(arr):"""堆排序。Args:arr: 待排序的数组。"""n = len(arr)

构建初始堆build_heap(arr)

循环取出堆顶元素for i in range(n - 1, 0, -1):

将堆顶元素与最后一个元素交换arr[i], arr[0] = arr[0], arr[i]

调整堆heapify(arr, i, 0) ```

总结堆排序是一种高效的排序算法，其时间复杂度稳定在 O(n log n)。它利用堆这种数据结构，通过不断地取出堆顶元素并调整堆来实现排序。堆排序是一种原地排序算法，只需要常数级别的额外空间。

优点* **时间复杂度稳定：** 堆排序的时间复杂度在最好、平均和最坏情况下都是 O(n log n)。 * **原地排序：** 堆排序只需要常数级别的额外空间。

缺点* **不稳定排序：** 堆排序可能会改变相等元素的相对顺序。 * **递归深度：** 堆排序的 `heapify()` 函数是递归调用的，可能会导致递归深度过深。