目录
前言：
1. 知识储备
1.1 大根堆与小根堆
1.1.1 小根堆
1.1.2 大根堆
1.2 向下调整与向上调整
1.2.1 向下调整 -- 多数利用于删除数据
1.2.2 向上调整 -- 多数利用于存入数据
2. 堆排序的基本步骤
3. 堆排序的代码实现
前言：
堆排序所要实现的需求：利用堆自n个元素中选取其中最大的k个元素。
提供实行条件的代码：
#include#include #include #include //堆排序 void PrintTopK(int* a, int n, int k) { // 1. 建堆--用a中前k个元素建堆 // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换 } void TestTopk() { int n = 10000; int* a = (int*)malloc(sizeof(int) * n); srand(time(0)); //通过使用随机函数与时间函数确定随机值 for (size_t i = 0; i < n; ++i) { a[i] = rand() % 1000000; //使得,随机值永远 < 1000000 } //使得有确定的10个最大值 a[5] = 1000000 + 1; a[1231] = 1000000 + 2; a[531] = 1000000 + 3; a[5121] = 1000000 + 4; a[115] = 1000000 + 5; a[2335] = 1000000 + 6; a[9999] = 1000000 + 7; a[76] = 1000000 + 8; a[423] = 1000000 + 9; a[3144] = 1000000 + 10; //堆排序 PrintTopK(a, n, 10); } int main() { TestTopk(); return 0; }
1. 知识储备
对于排序，无非就是分别大小，那么我们就得需要知晓什么是大根堆与小根堆。
对于排序，需要知晓基础的向上调整，与向下调整。
其次，便于讲解大根堆与小根堆，我们需要知道什么叫做父亲位，什么叫做孩子位，
下标计算父子间的关系：
- leftchild = parent * 2 + 1
- rightchild = parent * 2 + 2
- parent = (child - 1) / 2 (因为只会保留整数部分)
1.1 大根堆与小根堆
1.1.1 小根堆
- 小堆：父亲位，比孩子位，要小。
1.1.2 大根堆
- 大堆：父亲位，比孩子位，要大。
1.2 向下调整与向上调整
1.2.1 向下调整 -- 多数利用于删除数据
选出左右孩子中小的那一个。
以小的这个孩子跟父亲比较：
- 如果比父亲小，则交换，然后继续向下比较并调整。（最多调整到叶子节点就结束了）
- 如果比父亲大，则调整结束。
（父节点与子节点大小的比较，父对子）
//数据交换
void Swap(HeapDataType* e1, HeapDataType* e2)
{
int tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
//向下调整(小根堆)
void AdjustDwon(HeapDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child + 1] < a[child]) //在保证两个孩子都存在的同时，挑出最小的
{
++child;
}
if (a[child] < a[parent]) //孩子小于父亲即符合
{
Swap(&a[child], &a[parent]); //交换元素
parent = child;
child = parent * 2 + 1; //更改孩子的定义将原孩子变为下一个孩子
}
else
{
break; //孩子大于父亲，就没必要进行交换了。
}
}
}
1.2.2 向上调整 -- 多数利用于存入数据
- 如果比父亲小，则交换，然后继续向上比较并调整（最多调整到跟节点就结束了）。
- 如果比父亲大，则调整结束。
（父节点与子节点大小的比较，子对父）
//数据交换
void Swap(HeapDataType* e1, HeapDataType* e2)
{
int tmp = *e1;
*e1 = *e2;
*e2 = tmp;
}
//向上调整(小根堆)
void AdjustUp(HeapDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
2. 堆排序的基本步骤
基本思想：
首先：我们需要堆排序的主要目的是，排出最大的k个数，而大根堆就刚好类似。（但是，我们需要注意，大根堆实际的意义就是排出最大的一个值）这对于找到K个最大的数就是不利的了。然而，在结合向下调整与小根堆下可以完美实现。
如何利用向下调整：
向下调整经常利用于删除元素。
而小根堆的向下调整就是，利用于删除（第一个元素）堆元素的最小的元素。这也就代表，堆内的其他元素都要比我们所想要删除的元素大。这也就意味着，只要我们将比第一个元素大，就可以删除了，将那个比其大的放入，这样直至比较完，堆中所存储的值就是所有元素中最大的。
那么，我们就以k创建一个小堆，然后再将剩余的n-k个数据，利用向下调整。
3. 堆排序的代码实现
其中，我们会直接将k个元素进行存储，然后再进行排序为小根堆，我们需要运用一个算法：
//前面已经创建一个K个元素的无序堆
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdjustDwon(kMinHeap, k, i); //将K个元素进行排序
}
以最后一个父节点为根向下调整，这样有效提高效率，不然只有运用向上调整，这样每一个元素都要进行调整，会大大增加时间复杂度。
#include#include #include #include typedef int HeapDataType; //便于更改堆所存的数据的类型 typedef struct Heap { HeapDataType* a; //利用动态开辟所创建的一维数组 int size; //数据个数 int capacity; //空间大小 }HP; //数据交换 void Swap(HeapDataType* e1, HeapDataType* e2) { int tmp = *e1; *e1 = *e2; *e2 = tmp; } //向下存储 void AdjustDwon(HeapDataType* a, int size, int parent) { int child = parent * 2 + 1; while (child < size) { // 选出左右孩子中小/大的那个 if (child + 1 < size && a[child + 1] < a[child]) { ++child; } // 孩子跟父亲比较 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } //堆排序 void PrintTopK(int* a, int n, int k) { // 1. 建堆--用a中前k个元素建堆(建一个小堆) int* kMinHeap = (int*)malloc(k * sizeof(int)); assert(kMinHeap); for (int i = 0; i < k; ++i) { kMinHeap[i] = a[i]; //将k个元素直接进行存储 } for (int i = (k - 1 - 1) / 2; i >= 0; --i) { AdjustDwon(kMinHeap, k, i); //将K个元素进行排序 } // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换 for (int j = k; j < n; ++j) { if (a[j] > kMinHeap[0]) { kMinHeap[0] = a[j]; AdjustDwon(kMinHeap, k, 0); } } //将排出的最大的k个打印出来 for (int i = 0; i < k; ++i) { printf("%d ", kMinHeap[i]); } printf("n"); } void TestTopk() { int n = 10000; int* a = (int*)malloc(sizeof(int) * n); srand(time(0)); //通过使用随机函数与时间函数确定随机值 for (size_t i = 0; i < n; ++i) { a[i] = rand() % 1000000; //使得,随机值永远 < 1000000 } //使得有确定的10个最大值 a[5] = 1000000 + 1; a[1231] = 1000000 + 2; a[531] = 1000000 + 3; a[5121] = 1000000 + 4; a[115] = 1000000 + 5; a[2335] = 1000000 + 6; a[9999] = 1000000 + 7; a[76] = 1000000 + 8; a[423] = 1000000 + 9; a[3144] = 1000000 + 10; //堆排序 PrintTopK(a, n, 10); } int main() { TestTopk(); return 0; }
