每日算法题【二叉树】：堆的实现、堆排序的实现、文件中找TopK
(9)堆的实现
typedef int HPDataType;typedef struct Heap
{HPDataType* a; //堆结构是基于数组结构实现的int size; //数组下标int capacity; //数组容量
}Heap;//堆的初始化
void HeapInit(Heap* hp){assert(hp);hp->a = NULL;hp->size = hp->capacity = 0;
}// 堆的销毁
void HeapDestory(Heap* hp){assert(hp);free(hp->a);hp->a = NULL;hp->size = hp->capacity = 0;
}// 取堆顶的数据
HPDataType HeapTop(Heap* hp){assert(hp);assert(hp->size > 0);return hp->a[0];
}// 堆的数据个数
int HeapSize(Heap* hp){assert(hp);return hp->size;
}// 堆的判空
int HeapEmpty(Heap* hp){assert(hp);return hp->size == 0;
}////////////////////////////////////////////////////////////////////////////////////数据交换函数
void Swap(HPDataType* p1 , HPDataType* p2){//交换的是数组中两个地址指向的数据HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//////////////////////////////////////////////////////////////////////////////////向上调整算法
void AdjustUp(HPDataType* a,int child){int parent = (child - 1) / 2; //无论是奇偶子节点，均可以通过数组的下标“-1再/2”来获得父节点的下标//while (parent >= 0) 为了防止数组的越界访问，我们不采取这个循环条件while (child > 0){if (a[child] < a[parent]) //如果子节点小于父节点{Swap(&a[child], &a[parent]); //使用交换函数，交换父子的数据//当子节点与根节点完成交换之后，就归到其根节点的父节点所在的子树进行调整了//之前交换的父节点也就成为了也就成为了现在要调整的树的子节点child = parent; parent = (child - 1) / 2; //重新获取现在要调整的树的根节点 }else{break; //如果子节点大于父节点就不需要调整了}}
}// 堆的插入
void HeapPush(Heap* hp, HPDataType x){//判空assert(hp);//若空间不足则扩容if(hp->size == hp->capacity){int newcapacity = hp->capacity == 0 ? 4 : hp->capacity*2;//realloc记得传入要扩容的数组地址HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType)*newcapacity);if(tmp == NULL){perror("realloc fail");return ;}hp->a = tmp;hp->capacity = newcapacity;}//插入并向上调整hp->a[hp->size] = x;hp->size++;Adjustup(hp->a,hp->size-1);}//////////////////////////////////////////////////////////////////////////////////向下调整有一个大前提：左右子树必须已经是一个堆，才能调整
//向下调整算法--可以将数组恢复成堆的顺序--小根堆
void AdjustDown(HPDataType* a, int n, int parent){//传入的数组的地址和数组数据总个数还有根节点的位置//传入根节点的位置是因为需要调整的元素的位置就是根位置//利用假设法--先假设左孩子小，因为左孩子更不容易越界int child = parent * 2 + 1;//找到根节点的左子节点while(child < n){//child >= n 说明孩子不存在，已经调整到叶子节点了//找出两个子节点中较小的那个与根节点进行比较看是否要交换if(child + 1 < n && 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 HeapPop(Heap* hp){assert(hp);assert(hp->size > 0);Swap(&hp->a[0],&hp->a[hp->size-1]);hp->size--;AdjustDown(hp->a,hp->size,0);
}///////////////////////////////////////////////////////////////////////////////////
/*
//堆的创建，递归向下调整--大根堆当某个节点的值小于其子节点时，通过调整使其满足堆的性质。
void heapifyDown(heap* hp, int index) {int largest = index;//记录当前子树中最大值的索引int left = 2 * index + 1;int right = 2 * index + 2;//通过比较取得子树中最大的那个节点索引if (left < hp->size && hp->a[left] > hp->a[largest])largest = left;if (right < hp->size && hp->a[right] > hp->a[largest])largest = right;//如果最大值不是当前节点则调整，是则结束递归if (largest != index) {swap(&hp->a[index], &hp->a[largest]);//交换当前节点与最大子节点的值//这个时候largest指向的节点是换下来的小节点，而不是原先的最大子节点heapifyDown(hp, largest);//递到下一层调整被交换下去的小节点}
}
*/
(10)堆排序的实现
-
解题思路：
- 利用堆的根节点总是极值（大堆的根是最大值，小堆的根是最小值）的特性。每次将根节点（极值）与数组末尾元素交换，然后缩小堆的范围，并重新调整堆。交换到尾部才是最终结果，而堆结构中的数据是待排的。
// 向下调整算法（用于堆排序的大根堆版本） void AdjustDownForSort(int* a, int n, int parent) {int child = parent * 2 + 1;while (child < n) {// 找出较大的子节点（建大堆用于升序排序）if (child + 1 < n && a[child + 1] > a[child]) {++child;}// 如果子节点大于父节点，则交换（大堆性质）if (a[child] > a[parent]) {Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;} else {break;}} }// 高效的堆排序（升序）- 原地排序，O(1)空间复杂度 void HeapSortInPlace(int* arr, int n) {// 步骤1：从最后一个非叶子节点开始，构建大根堆// 注意：这里建大堆是为了升序排序for (int i = n / 2 - 1; i >= 0; i--) {AdjustDownForSort(arr, n, i);}// 步骤2：依次将堆顶元素（最大值）与末尾元素交换，并调整堆for (int i = n - 1; i > 0; i--) {Swap(&arr[0], &arr[i]); // 将最大值放到数组末尾AdjustDownForSort(arr, i, 0); // 调整剩余部分为大堆} }
(11)文件中找TopK问题
-
解题思路：
-
用数据集合中前K个元素来建堆O(K)
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆 -
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素O(logK * (N-K))
将剩余N-K个元素依次与堆顶元素比较，如果比堆顶(k个中最小的元素)元素大则进行替换，替换完进行向下调整，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 -
TopK算法O(N logK)
- 为什么使用小顶堆？
- 我们要找最大的k个数
- 维护一个大小为k的小顶堆，堆顶是这k个数中的最小值
- 当新数大于堆顶时，替换堆顶并调整，确保堆中始终是目前遇到的最大的k个数
// Top-k方法：从海量数据中找出最大的k个数 void Topk() {int k;printf("请输入k>:");scanf("%d", &k); // 用户输入要查找的最大数的个数k// 动态分配大小为k的数组，用于存储前k个最大的数（使用小顶堆结构）int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail"); // 内存分配失败处理return;}const char* file = "data.txt"; // 数据文件路径FILE* fout = fopen(file, "r"); // 以只读方式打开数据文件if (fout == NULL){perror("fopen error"); // 文件打开失败处理return;}// 读取文件中前k个数到数组中for (int i = 0; i < k; i++){fscanf(fout, "%d", &kminheap[i]); // 从文件读取整数到数组}// 将前k个数构建成小顶堆// 从最后一个非叶子节点开始向前调整// (k - 1 - 1) / 2 计算最后一个非叶子节点的索引：// k-1是最后一个元素的索引，(index-1)/2得到其父节点索引for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i); // 向下调整建堆}// 读取文件中剩下的N-K个数（N为文件总数据量）int x = 0; // 临时变量，用于存储从文件读取的每个数while (fscanf(fout, "%d", &x) > 0) // 成功读取一个数时继续循环{// 核心算法：如果当前数大于堆顶（小堆的最小值）if (x > kminheap[0]){kminheap[0] = x; // 用更大的数替换堆顶AdjustDown(kminheap, k, 0); // 重新调整堆，保持小顶堆性质}// 如果当前数小于等于堆顶，直接忽略（不可能是前k大的数）}// 输出结果：此时堆中存储的就是最大的k个数printf("最大前%d个数：", k);for (int i = 0; i < k; i++){printf("%d ", kminheap[i]); // 输出前k大的数}printf("\n");// 注意：这里应该添加内存释放和文件关闭free(kminheap);fclose(fout); }
-
void CreateNDate()
{// 造数据int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}