数据结构堆排序代码
数据结构中堆是一种特殊的树形数据结构，可用于实现优先队列。堆排序是一种非常高效的排序算法，其时间复杂度为O(nlogn)。堆排序的基本思想是将待排序序列构建成一个大根堆或小根堆，然后依次将堆顶元素取出，即可得到排序结果。本文将从算法原理、代码实现和应用场景三个方面介绍堆排序。
算法原理
堆有两种：大根堆和小根堆。在大根堆中，父节点的值必须大于或等于其子节点的值。而在小根堆中，父节点的值必须小于或等于其子节点的值。堆排序以大根堆为例。
堆排序的核心思路是构建大根堆并依次将堆顶元素取出。首先需要将待排序序列构建成大根堆。构建大根堆的过程可以采用从后往前遍历（即从最后一个非叶子节点开始），将每个子树调整为大根堆的算法，得到一个初始的大根堆。接着，将堆顶元素取出并与堆底元素交换位置，然后对剩余的节点进行调整，使其重新满足大根堆的性质。重复执行上述步骤，直至待排序序列所有元素被依次取出。
代码实现
以下是C++实现堆排序的代码：
```
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
std::swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
```
应用场景
堆排序有许多应用场景。由于堆排序具有良好的时间复杂度和空间复杂度，可以被广泛地应用于数据处理和存储中。比如：
1. 打牌游戏中洗牌：在洗牌的过程中，需要将一副牌随机排列。可以用堆排序实现。
2. 优先队列：从一个包含若干个元素的集合中不断取元素的过程可以用优先队列实现。而堆排序恰好可以用来实现优先队列。
3. 寻找数据流中第k大的元素：假设有一个数据流，其中有大量的元素，如何快速得到数据流中第k大的元素呢？可以使用堆排序，即构建大小为k的小根堆，不停地将新的元素加入小根堆，当小根堆满了之后，若新元素的值比小根堆堆顶元素小，则将其替换掉堆顶元素，然后重新构建小根堆。这样，在所有元素都加入小根堆之后，小根堆的堆顶元素即为数据流中第k大的元素。
