1.堆的概念与结构
如果有⼀个关键码的集合 ，把它的所有元素按完全⼆叉树的顺序存储⽅ 式存储，在⼀个⼀维数组中，并满⾜： （ 且 ）， i = 0、1、2... ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆 叫做最⼩堆或⼩根堆。
2.堆的性质
• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；
• 堆总是⼀棵完全⼆叉树。
3.堆的实现
3.1初始化及基础功能
typedef struct heap
{int* a;int size;int capacity;
}HP;void heapinit(HP* php)
{assert(php);php->a = NULL;php->size = 0;php->capacity = 0;
} //初始化void swap(int* p1, int* p2)
{int t = 0;t = *p1;*p1 = *p2;*p2 = t;
} //交换函数void heappush(HP* php, int data)
{if (php->size == php->capacity) //如果内存空间满了{int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2; //内存空间和元素数量一样》》》》》1.内存空间为0，令内存大小为4， 2.内存空间满了，扩容至两倍大int* tmp = (int*)realloc(php->a, newcapacity * sizeof(int)); //开辟内存空间记得加sizeof(sldatatype) php->a = tmp; //开辟内存空间赋给a指针php->capacity = newcapacity; //设置新的容量}php->a[php->size] = data;php->size++;adjustup(php->a, php->size - 1);
}void heappop(HP* php)
{swap(&php->a[0],&php->a[php->size - 1]);php->size--;adjustdown(php->a,php->size-1,0);//首尾互换！！！！！！，可以保证根节点以下的二叉树均不被改变（即排好序），只需由新的根节点从上往下排序交换一轮
}bool heapempty(HP* php)
{return php->size == 0;
} //判断是否为空int heaptop(HP* php)
{assert(php);return php->a[0];
} //取根节点3.2 向上调整算法
向上调整算法
• 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后
• 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可
（要求插入前必须是堆）！！！！！！
void adjustup(int* a, int child) //向上调整法 //上方必须是堆
{int parent = (child-1)/2;while (child>0){if (a[parent]<=a[child]) //小堆为>=,大堆为<={swap(&a[parent],&a[child]);child = parent;parent = (child - 1)/2;}else{break;}}
}3.3 向下调整算法
向下调整算法
• 将堆顶元素与堆中最后⼀个元素进⾏交换
• 删除堆中最后⼀个元素
• 将堆顶元素向下调整到满⾜堆特性为⽌
！！！！！！向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。
void adjustdown(int* a,int n, int parent) //向下调整法，！！！！！！（仅适用于根结点两端都是大堆或小堆）
{int child = 2 * parent + 1;while (child<=n) //{if (child + 1<=n && a[child + 1] > a[child]) // child+1>n可以推出child==n，所以只有左孩子{child++; //选出左右孩子中最大的一个‘>’,最小的为'<'}if (a[parent]<=a[child]) //大堆为“<=”,小堆为“>=”{swap(&a[parent], &a[child]);parent = child;child = 2 * parent + 1; //每次都先找左孩子}else{break;}}
}
4.堆排序
int main()
{int a[] = { 65,100,70,32,50,35 };int i;int n = sizeof(a) / sizeof(a[0]);int flag = n;for (i = 1; i < sizeof(a) / sizeof(a[0]); i++) //i从1开始，因为只有一个元素时可以视作堆{adjustup(a, i);} //升序排序前的第一步，建立大堆,i从1开始，因为i=0时可视作堆，从1开始向上调整//记住，只是建好了堆，堆不代表直接打印出来是有序的！！！！！！！！！还需要调整while (n>0) //上文所说的调整，因为是大堆，所以root一定是最大的{swap(&a[0],&a[n-1]);//将最大的换到tailn--; //不再关注最大的tailadjustdown(a,n-1, 0);//排除tail后重新建立大堆，选择从根开始的向下调整最合适（交换后，根的左右两边都是堆，只是根变了），让第二大的变为root，循环} for (i = 0; i <= flag - 1; i++)printf("%d ",a[i]);return 0;
}5.实际问题解决 ——topK问题
TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。 ⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了 (可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决，基本思路如下：
1）⽤数据集合中前K个元素来建堆
前k个最⼤的元素，则建⼩堆
前k个最⼩的元素，则建⼤堆
2）⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素
将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素
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);
}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){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 建k个数据的⼩堆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]);}fclose(fout);
}
