重生之我在异世界学编程之算法与数据结构：深入堆篇
大家好，这里是小编的博客频道
小编的博客：就爱学编程
很高兴在ZEEKLOG这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！本文目录
那接下来就让我们开始遨游在知识的海洋！
正文
一、堆的基本概念
堆是一种特殊的树形数据结构，它完全是一棵二叉树。堆分为最大堆和最小堆两种类型：
最大堆：在最大堆中，父节点的键值总是大于或等于任何一个子节点的键值。换句话说，根节点是整个堆中键值最大的节点。最小堆：在最小堆中，父节点的键值总是小于或等于任何一个子节点的键值。也就是说，根节点是整个堆中键值最小的节点。
堆通常用于实现优先队列，并且能在对数时间内完成插入、删除以及查找最值等操作。
二、堆的存储表示
堆一般使用数组来实现，这是因为堆是完全二叉树的一种特殊形式，其性质使得我们可以利用数组的索引关系来方便地表示堆的结构。对于一个包含n个元素的零基数组来说：
对于任意给定的索引i：
左子节点的索引为(2*i + 1)
右子节点的索引为(2*i + 2)
父节点的索引为((i - 1) / 2)（注意这是整数除法）
这种表示方法使得堆的操作变得非常简单高效。
三、堆的基本操作
1. 插入元素（Insert）
向堆中插入一个新元素的过程如下：
将新元素添加到堆的末尾（即数组的最后一个位置）。
然后，从该位置开始向上调整堆，以维护堆的性质。这通常是通过“上浮”（bubble up）或“筛选”（sift up）操作来实现的。
具体步骤如下（以最大堆为例）：
voidheapInsert(int arr[],int&heapSize,int element){// Step 1: Add the new element at end arr[heapSize]= element; heapSize++;// Step 2: Fix the max heap property if it is violatedint i = heapSize -1;while(i !=0&& arr[(i -1)/2]< arr[i]){// Swap current node with its parentswap(&arr[i],&arr[(i -1)/2]); i =(i -1)/2;// Move to parent index}}2. 删除最大/最小值（Extract Max/Min）
从堆中删除最大或最小值的过程如下（以最大堆为例）：
将根节点（即最大值）与堆的最后一个元素交换。
减少堆的大小（即将堆的最后一个元素移除）。
从新的根节点开始向下调整堆，以维护堆的性质。这通常是通过“下沉”（bubble down）或“筛选”（sift down）操作来实现的。
具体步骤如下：
intheapExtractMax(int arr[],int&heapSize){if(heapSize <=0)return INT_MIN;// Return an invalid value if heap is empty// Store the maximum value, and remove it from heapint root = arr[0]; arr[0]= arr[heapSize -1]; heapSize--;// Fix the max heap property if it is violatedmaxHeapify(arr,0, heapSize);return root;}voidmaxHeapify(int arr[],int i,int heapSize){int largest = i;// Initialize largest as rootint left =2* i +1;// left child indexint right =2* i +2;// right child index// If left child is larger than rootif(left < heapSize && arr[left]> arr[largest]) largest = left;// If right child is larger than largest so farif(right < heapSize && arr[right]> arr[largest]) largest = right;// If largest is not rootif(largest != i){swap(&arr[i],&arr[largest]);// Recursively heapify the affected sub-treemaxHeapify(arr, largest, heapSize);}}3. 构建堆（Build Heap）
将一个无序数组构建成一个堆的过程可以通过以下步骤实现：
从最后一个非叶子节点开始，依次对每个节点执行“下沉”操作，直到根节点为止。
具体步骤如下（以最大堆为例）：
voidbuildMaxHeap(int arr[],int n){int startIdx =(n /2)-1;// Last non-leaf nodefor(int i = startIdx; i >=0; i--){maxHeapify(arr, i, n);}}四、源码
注意：这是小编自己写的，可能有不足之处，仅供参考！！！
（1）heap.h
#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint HPDataType;typedefstructHeap{ HPDataType* _a;int _size;int _capacity;}Heap;//堆的初始化voidHeapInit(Heap* php);// 堆的销毁voidHeapDestory(Heap* hp);// 堆的插入voidHeapPush(Heap* hp, HPDataType x);// 堆的删除voidHeapPop(Heap* hp);// 取堆顶的数据 HPDataType HeapTop(Heap* hp);// 堆的数据个数intHeapSize(Heap* hp);// 堆的判空intHeapEmpty(Heap* hp);//对调voidSwap(HPDataType* ptr1, HPDataType* ptr2);//向上调整（使用条件：除了child对应的数据，其他的构成堆）voidAujustUp(HPDataType* a,int child);//向下调整（使用条件：左右子树都是大堆或小堆）voidAujustDown(HPDataType* a,int size,int parent);（2）heap.c
#include"heap.h"//堆的初始化voidHeapInit(Heap* php){assert(php); HPDataType* temp =(HPDataType*)malloc(sizeof(HPDataType)*4);if(temp ==NULL){perror("malloc fail");return;} php->_a = temp; php->_capacity =4; php->_size =0;}// 堆的销毁voidHeapDestory(Heap* php){assert(php);free(php->_a); php->_a =NULL; php->_capacity =0; php->_size =0;}//对调voidSwap(HPDataType* ptr1, HPDataType* ptr2){assert(ptr1 && ptr2); HPDataType temp =*ptr1;*ptr1 =*ptr2;*ptr2 = temp;}//向上调整（使用条件：除了child对应的数据，其他的构成堆）voidAujustUp(HPDataType* a,int child){assert(a);int parent =(child -1)/2;while(child >0){if(a[child]> a[parent]){Swap(&a[child],&a[parent]);}else{break;} child = parent; parent =(child -1)/2;}}// 堆的插入（从尾插入，向上调整）voidHeapPush(Heap* php, HPDataType x){assert(php);if(php->_capacity == php->_size){ HPDataType* temp =(HPDataType*)realloc(php->_a,sizeof(HPDataType)*2* php->_capacity);if(temp ==NULL){perror("realloc fail");return;} php->_a = temp; php->_capacity *=2;} php->_a[php->_size]= x;++php->_size;AujustUp(php->_a, php->_size -1);}//向下调整（使用条件：左右子树都是大堆或小堆）voidAujustDown(HPDataType* a,int size,int parent){assert(a);int bigchild = parent *2+1;//先假设大孩子是左孩子while(bigchild < size){//先找到真正数值大的孩子的下标if(bigchild +1< size && a[bigchild]< a[bigchild +1])//小堆'<'改成'>'{++bigchild;}if(a[bigchild]> a[parent]){//小堆'>'改成'<'Swap(&a[bigchild],&a[parent]); parent = bigchild; bigchild = parent *2+1;//还是先假设大孩子是左孩子}else{break;}}}// 堆的删除（删掉堆顶，向下调整）voidHeapPop(Heap* php){assert(php && php->_size);//采用堆顶数据和堆尾数据对调，再向下调整的优势在于效率高，且不会改变大部分的父子关系Swap(&php->_a[0],&php->_a[php->_size -1]);--php->_size;AujustDown(php->_a, php->_size,0);}//voidHeapInitArray(Heap* php,int* a,int n){assert(php); php->_a =(HPDataType*)malloc(sizeof(HPDataType)* n);if(php->_a ==NULL){perror("malloc fail");return;} php->_size = n; php->_capacity = n;// 建堆for(int i =(n -2)/2; i >=0;--i){AdjustDown(php->_a, php->_size, i);}}// 取堆顶的数据 HPDataType HeapTop(Heap* php){assert(php && php->_size);return php->_a[0];}// 堆的数据个数intHeapSize(Heap* php){assert(php && php->_size);return php->_size;}// 堆的判空intHeapEmpty(Heap* php){assert(php);return php->_size ==0;}（3）Test.c
#define_CRT_SECURE_NO_WARNINGS#include"heap.h"intmain(){ Heap heap;//堆的初始化HeapInit(&heap);//堆插入HeapPush(&heap,1);HeapPush(&heap,2);HeapPush(&heap,17);HeapPush(&heap,16);HeapPush(&heap,18);HeapPush(&heap,111);HeapPush(&heap,21);HeapPush(&heap,14);HeapPush(&heap,61);//堆删除HeapPop(&heap);HeapPop(&heap);HeapPop(&heap);HeapPop(&heap);//根据自己需求观察堆内数据（大堆）int k =0;scanf("%d",&k);while(!HeapEmpty(&heap)&& k--){printf("%d ",HeapTop(&heap));HeapPop(&heap);}printf("\n");return0;}五、堆的应用
1. 优先队列
堆是实现优先队列的理想数据结构。在优先队列中，每个元素都有一个优先级，出队顺序是按照优先级的高低来进行的。最大堆可以用于实现一个最大优先队列，而最小堆则可以用于实现一个最小优先队列。
2. 堆排序
- 堆排序是一种基于堆的比较排序算法。它的基本思想是先将待排序序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的元素。然后将其与末尾元素交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
堆排序的具体步骤如下：
构建最大堆（Build Max Heap）：将待排序序列构造成一个大顶堆。
交换堆顶元素与末尾元素（Swap and Reduce Heap Size）：将当前堆顶元素（最大值）与末尾元素交换，并将堆的大小减1。
重新调整堆（Heapify）：对新的堆顶元素进行调整，使其满足堆的性质。
重复步骤2和3，直到堆的大小为1。
具体代码实现如下：
#include<stdio.h>#include<stdlib.h>// Function to swap two elementsvoidswap(int* a,int* b){int t =*a;*a =*b;*b = t;}// Function to heapify a subtree rooted with node i which is an index in arr[]voidheapify(int arr[],int n,int i){int largest = i;// Initialize largest as rootint left =2* i +1;// left = 2*i + 1int right =2* i +2;// right = 2*i + 2// See if left child of root exists and is greater than rootif(left < n && arr[left]> arr[largest]) largest = left;// See if right child of root exists and is greater than rootif(right < n && arr[right]> arr[largest]) largest = right;// Change root, if neededif(largest != i){swap(&arr[i],&arr[largest]);// Heapify the root.heapify(arr, n, largest);}}// Main function to do heap sortvoidheapSort(int arr[],int n){// Build heap (rearrange array)for(int i = n /2-1; i >=0; i--)heapify(arr, n, i);// One by one extract an element from heapfor(int i = n -1; i >=0; i--){// Move current root to endswap(&arr[0],&arr[i]);// call max heapify on the reduced heapheapify(arr, i,0);}}// A utility function to print array of size nvoidprintArray(int arr[],int n){for(int i =0; i < n;++i)printf("%d ", arr[i]);printf(" ");}// Driver program to test above functionsintmain(){int arr[]={12,11,13,5,6,7};int n =sizeof(arr)/sizeof(arr[0]);printf("Unsorted array: ");printArray(arr, n);heapSort(arr, n);printf("Sorted array: ");printArray(arr, n);return0;}3.Top K问题
（1）定义与背景
- 定义：给定一个数据集，要求找出其中前K个最大（或小）的元素。
- 背景：该问题在多个领域有广泛应用，如搜索引擎优化、电商推荐系统、异常检测等。在这些场景中，通常需要快速地从大量数据中提取出最重要的信息。
（2）应用场景
- 搜索引擎：根据用户输入的关键词，返回最相关的Top K个网页链接。这些链接通常是根据页面的相关性、权威性、用户点击率等因素综合评定的。
- 电商推荐：为用户提供前K个最热门或最符合其偏好的商品推荐。这有助于提升用户体验和销售转化率。
- 排行榜：在体育比赛、学术排名、企业榜单等领域，使用Top K来列出表现最佳的前几名。
- 异常检测：在金融风控、网络安全等领域，通过分析数据中的Top K异常值，及时发现潜在的风险和威胁。
- 科学研究：在生物信息学、物理学等领域，通过分析Top K的数据，可以发现关键的科学问题或现象。
- 社会媒体分析：分析社交媒体上的热门话题、影响力人物等，为公关策略和市场营销提供依据。
- 教育评估：在学校和教育机构中，通过分析学生的成绩分布，识别出表现优异的学生或需要额外关注的学生群体。
（3）实现方法
- 排序法：对整个数据集进行排序，然后选取前K个元素。这种方法简单直观，但当数据集非常大时，排序过程可能会非常耗时，时间复杂度为O(
nlogn)。 - 堆排序：使用最小堆（
Min-Heap）或最大堆（Max-Heap）来维护当前的前K大（或小）元素。当遍历到新的元素时，如果它大于（或小于）堆顶元素，则替换堆顶并调整堆。最终，堆中的元素即为所求的前K大（或小）元素。这种方法的时间复杂度为O(nlogk)，适合处理大规模数据。- 初始化一个大小为K的堆。
- 如果堆的大小小于K，直接插入新元素。
- 如果堆的大小等于K，且当前元素大于（对于找前K大）或小于（对于找前K小）堆顶元素，则替换堆顶并调整堆。
- 遍历完成后，堆中的元素即为所求。
- 快速选择（QuickSelect）：这是一种基于快速排序的选择算法，可以在平均O(n)时间内找到第K大的元素，进而得到Top K。不过，其最坏情况下的时间复杂度仍为O(n^2)。
- 计数排序和桶排序：对于特定范围的数据，可以使用这两种排序方法来高效地找到Top K。它们通过将数据分配到不同的桶或计数数组中，然后统计每个桶或数组中的元素数量来找到Top K。
- 近似算法：在一些对精度要求不高的场景下，可以使用近似算法来快速得到Top K。例如，Min-Hash算法可以用于频繁项集挖掘。
（4）算法优化与挑战
- 优化：在实际应用中，可以通过多种方式来优化Top K算法的性能。例如，利用并行计算能力加速数据处理；使用高效的内存管理机制减少内存消耗；结合数据的特性选择合适的算法和数据结构等。
- 挑战：在处理大数据时，Top K算法面临的主要挑战包括计算效率和存储空间。随着数据量的增加，传统的排序方法会变得非常低效，而且可能需要大量的内存来存储中间结果。因此，需要采用更加高效的算法和数据结构来解决这些问题。
综上所述，Top K问题是一个具有广泛应用背景和重要价值的问题。通过理解和掌握其相关知识，可以更好地分析和理解数据，提高决策效率和质量。
代码实现：
#define_CRT_SECURE_NO_WARNINGS//TOP-k问题//想要找出N个数据中最大（小）的K个：最简单的思路就是排序，但排序在数据量很大的时候效率低下且有可能无法全部加载进内存。最好的办法就是用堆的办法。//用堆也有两种思路：（1）把N个数据全部建大（小）堆，然后再top后popK次-----不足：数据只能全部在内存上，在数据量很大时数据可能无法全部加载进内存；//（2）把前K个数据建小（大）堆，然后再使剩余的N-K个数据依次与堆顶进行比较，比它大就取代，再向下调整。到最后剩下的数据就是最大（小）的K个。#include<stdio.h>#include<assert.h>#include<time.h>#include<stdlib.h>//对调数据voidSwap(int* ptr1,int* ptr2){int temp =*ptr1;*ptr1 =*ptr2;*ptr2 = temp;}//向上调整（使用条件：除了child对应的数据，其他的构成堆）voidAdjustUp(int* a,int child){assert(a);int parent =(child -1)/2;while(child >0){if(a[child]> a[parent]){Swap(&a[child],&a[parent]);}else{break;} child = parent; parent =(child -1)/2;}}//向下调整（使用条件：左右子树都是大堆或小堆）voidAdjustDown(int* a,int size,int parent){assert(a);int bigchild = parent *2+1;//先假设大孩子是左孩子while(bigchild < size){//先找到真正数值大(小)的孩子的下标if(bigchild +1< size && a[bigchild]> a[bigchild +1])//小堆后面的'<'改成'>'{++bigchild;}if(a[bigchild]< a[parent]){//小堆'>'改成'<'Swap(&a[bigchild],&a[parent]); parent = bigchild; bigchild = parent *2+1;//还是先假设大孩子是左孩子}else{break;}}}//造数据voidCratedata(int n){srand(time(0));//生成随机数 FILE* fin =fopen("data.txt","w");if(NULL== fin){perror("fopen error");return;}while(n--){int data =rand()%10000;fprintf(fin,"%d\n", data);}fclose(fin);}//Top-K（第二种解决办法）voidTop_k(int n,int k){//1.读取前K个数据并建堆//打开文件 FILE* fout =fopen("data.txt","r");if(NULL== fout){perror("fopen error");return;}//申请空间存储读取的K个数据int* a =(int*)malloc(sizeof(int)* k);assert(a);for(int i =0; i < k; i++){fscanf(fout,"%d",&a[i]);}//把这K个数据进行建堆----找最大，建小堆(向下调整)----可以防止数据的进入堆不受阻for(int i =(k -1-1)/2; i >0;--i){AdjustDown(a, k, i);}//2.然后再使剩余的N-K个数据依次与堆顶进行比较，比它大就取代，再向下调整。到最后剩下的数据就是最大（小）的K个。int data =0;while(fscanf(fout,"%d",&data)!=EOF){if(data > a[0]){ a[0]= data;AdjustDown(a, k,0);}}fclose(fout);for(int i =0; i <10; i++){printf("%d ", a[i]);}}voidTest(){//Cratedata(100);Top_k(100,10);}intmain(){Test();return0;}六、总结
- 堆是一种非常重要的数据结构，它在计算机科学中有着广泛的应用。通过理解堆的基本概念、存储表示和基本操作，我们可以更好地掌握堆的使用方法和应用场景。同时，堆排序作为一种高效的比较排序算法，也值得我们深入学习和掌握。希望本文能够帮助大家更好地理解C语言中的数据结构——堆。
