一、概念及结构堆是一种特殊的树形数据结构通常表现为一棵完全二叉树是用二叉树的顺序存储方式来存储元素的。堆分为小堆和大堆1.1 小堆父结点小于子结点但是父结点下面的两个子结点没大小区分。1.2 大堆父结点大于子结点但是父结点下面的两个子结点没大小区分。二、建堆小堆示例2.1 向上调整建堆适用于一边插入一边建堆的情况。插入节点后找到它的父结点让父结点与它进行比较如果小于它则退出如果大于则交换位置重复上述操作直至循环结束或跳出循环。void AdjustUp(int* arr, int child) { int parent (child - 1) / 2; while (child 0) { if (arr[child] arr[parent])//改为 建大堆 { Swap(arr[child], arr[parent]); child parent; parent (child - 1) / 2; } else { break; } } }注Swap是交换位置函数。void Swap(int* p1, int* p2) { int temp *p1; *p1 *p2; *p2 temp; }2.2 向下调整建堆适用于对父节点进行调整。先找到较小的那个孩子让该孩子与它进行比较如果孩子大于它则退出如果小于则交换位置重复上述操作直至循环结束或跳出循环。void AdjustDown(int* arr, int n, int parent) { int child (parent * 2) 1;//先默认找到左孩子 while (child n) { //判断左孩子是否大于右孩子child 1 n防止非法访问 if (child 1 n arr[child 1] arr[child]) child; if (arr[parent] arr[child]) { Swap(arr[parent], arr[child]); parent child; child (parent * 2) 1; } else { break; } } }三、TOPK问题TOPK问题即求数据结合中前K个最大的元素或者最小的元素。一般来说数据量比较大。如果有一个数组数组里有N个数据我们要找最大的前K个数据要怎么做呢3.1 法一先整体建立一个大堆然后让根节点与该堆的最后一个节点交换然后拿取该堆最后的结点再让根结点向下调整。重复上述操作K次。void Heapsort(int* a, int n) { int k 0; scanf(%d, k); for (int i 0; i n; i) AdjustUp(a, i); while (k--) { Swap(a[n - 1], a[0]); AdjustDown(a, n - 1, 0); n--; } }3.2 法二先从数组中取前k个数建立一个小堆然后遍历后面的元素后与堆顶元素比较如果大于则进行交换然后向下调整。最后拿出该堆即可。void Heapsort(int* a, int n) { int k 0; scanf(%d, k); for (int i (k - 2) / 2; i 0; i--) AdjustDown(a, k, i); for (int i k; i n; i) { if (a[i] a[0]) { Swap(a[i], a[0]); AdjustDown(a, k, 0); } } }(k - 2) / 2是为了拿到该堆中最后一个父节点的下标子节点的下标求出父节点的下标的公式是 (i - 1) / 2 但是这里 k - 1 先当于是最后一个孩子节点的下标所以是 (k - 2) / 2。