数据结构之树&&二叉树(三)

前言

堆是考研 408、算法面试里的高频考点，很多同学在这里踩坑：误以为建堆复杂度是\\(O(n\\log n)\\)、分不清 TopK 该用大根堆还是小根堆、不清楚堆排序为什么不稳定。本文从原理推导、算法流程、代码实现、易错点全方位讲解堆的三大核心考点。

建堆效率问题

1. 两种建堆方式（核心区分！）

方式 1：批量原地建堆（考研默认建堆，自底向上adjustDown向下调整）

操作流程 给定一个原始数组，我们直接把数组看作一棵完全二叉树。 从最后一个非叶子结点开始，向前遍历到根节点，对每一个节点执行向下调整siftDown操作。 向下调整：如果当前节点不满足堆性质（大根堆：父≥子），就和孩子中更大的节点交换，然后继续往下递归，直到满足堆性质。

方式 2：逐个插入建堆（自顶向上adjustUp向上调整）

从空堆开始，依次把数组每一个元素插入堆，每次插入放在数组末尾，执行向上调整。 每一次插入，最坏需要\\(\\log n\\)次调整，一共n个元素。

堆排序

1. 算法思想

堆排序利用大根堆堆顶永远是当前序列最大值这个特性。 整体分两大阶段：

最终数组从前往后，从小到大有序。

解决top  k问题

1. 问题描述

给定n个数字，找出前 K 大（或者前 K 小）的 K 个元素。

重点场景：海量数据，n极大，无法一次性全部加载进内存，流式读取数据。

以【求数组前 K 大元素】举例讲解：

调试技巧,我们对创造的随机数是有范围的,那么我们之后直接在那个文件里面再某些数据后面加上一些0,就可以知道前几大的元素是什么

void topk() {
printf("请输入k：");
int k = 0;
scanf("%d", &k);
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL) {
// 打开文件失败
perror("fopen error");
return;
}
////////
int val = 0;
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL) {
// malloc失败
perror("malloc error");
return;
}
//将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, k, i);
}
int x = 0;
while (fscanf(fout, "%d", &x) != EOF) {
if (x > minheap[0])
{
minheap[0] = x;
AdjustDown(minheap, k, 0);
}
}
for (int i = 0; i < k; i++) {
printf("%d ", minheap[i]);
}
free(minheap);
fclose(fout);

}