数据结构:Heap堆应用（堆排序，TOP-K问题）手把手带你入门数据结构~

---

前言

在学习了堆之后，我们一起来看一看堆的应用~

---

一、堆排序

1. 数据入堆

想要让一组数据进行堆排序，我们来想一想，像下面这一组数据要怎么建堆?

这是一个乱序的数组，将每一个数组的元素取出来向上调整建堆。

排成如下图所示的样子，就完成数据入堆了~

for (int i = 0; i < n; i++)
{AdjustUp(arr, i);
}

---

2. 堆排序

现在我们已经有了一个小根堆，那么我们就可以将堆排成降序结构。

小根堆排降序
大根堆排升序

//循环将堆顶数据跟最后位置（会变化，每次减少一个数据）的数据进行交换
int end = n - 1;
while (end > 0)
{Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;
}

void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子//while (parent < n)while (child < n){//小堆：找左右孩子中找最小的//大堆：找左右孩子中找大的if (child + 1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换{//建大堆，>//建小堆，<if (arr[child] < arr[parent]){Swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}

---

3. 时间复杂度

（1）冒泡排序时间复杂度

时间复杂度为O（n^2）

//冒泡排序
//时间复杂度：0(N^2)
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){//升序if (arr[j] > arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}

---

（2）向上调整建堆的时间复杂度

从这张图可以简单分析得知，向上调整的时间复杂度是log n,而循环有n次，因此时间复杂度为log n。

for (int i = 0; i < n; i++)
{AdjustUp(arr, i);
}

那么堆排序和冒泡排序的差距有多大呢?我们看下面这张图。

因此堆排序的效率高。

下面我们严谨证明一下向下调整算法建堆的时间复杂度：

---

（3）向下调整建堆的时间复杂度

那么向下调整怎么建堆呢?

向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。

向下调整算法
• 将堆顶元素与堆中最后⼀个元素进⾏交换
• 删除堆中最后⼀个元素
• 将堆顶元素向下调整到满⾜堆特性为⽌

//向下调整算法建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{AdjustDown(arr, i, n);
}

接下来我们来推理一下向下调整建堆的时间复杂度。

所以用向下调整建堆的方法更优

因此堆排序的时间复杂度为 O（n* log n）~

---

4. 堆排序总结

//堆排序
//空间复杂度为0(1)
//时间复杂度为O(n*logn)
void HeapSort(int* arr, int n)
{//建堆//升序---大堆//降序----小堆//for (int i = 0; i < n; i++)//{//	AdjustUp(arr, i);//}//向下调整算法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}//循环将堆顶数据跟最后位置（会变化，每次减少一个数据）的数据进行交换int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}

---

二、TOP-K问题

1. TOP-K问题背景

TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。

⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了(可能数据都不能⼀下⼦全部加载到内存中)。

---

2. TOP-K问题解决方法

1）⽤数据集合中前K个元素来建堆.

前k个最⼤的元素，则建⼩堆
前k个最⼩的元素，则建⼤堆

2）⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素
将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素.

3. 创建庞大的数据

将数据写到文件中，为了方便观察，我们可以手动改几个数据

void CreateNDate()
{// 造数据int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}

---

4. TOP-K问题的解决

void TOPk()
{int k = 0;printf("请输入k:");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen fail!");exit(1);}int* minHeap = (int*)malloc(k * sizeof(int));if (minHeap == NULL){perror("malloc fail!");exit(2);}//从文件中读取前K个数据for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//建堆---小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minHeap, i, k);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){//读取到的数据跟堆顶的数据进行比较//比堆顶值大，交换入堆if (x > minHeap[0]){minHeap[0] = x;AdjustDown(minHeap, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}fclose(fout);
}

---

总结

通过上述讲解，相信大家对堆的经典问题已经有了大概的了解，观众老爷们下去要多多练习，感谢支持！

真相永远只有一个！