目录一、堆的概念及结构二、堆的实现1.堆的向下调整算法2.堆的创建3.堆的插入4.堆的删除5.堆的代码实现完整代码三、堆的应用1.堆排序2.TOP-K问题一、堆的概念及结构如果有一个关键码的集合K {k1,k2,……,kn-1}把它的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中并满足KiK(2*i1)且KiK(2i2)或KiK(2*i1)且KiK(2i2)I1,0,2……则称为小堆大堆。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。堆的性质堆中某个结点的值总是不大于或不小于其父结点的值。堆总是一棵完全二叉树二、堆的实现1.堆的向下调整算法向下调整算法有一个前提左右子树必须是一个堆才能调整。由于根节点的左右子树为空因此根节点本身就可以看作是一个堆所以我们可以从完全二叉树的最后一个非叶子节点开始向下调整算法。如果建小堆根节点比左右子树大时将根节点和左右子树的根节点中的较小值交换位置再检查左右子树是否仍符合堆的性质不符合就继续使用向下调整算法直到完全符合堆的性质。// 向下调整算法 void AdjustDown(HPDataType* a, int n, int parent);void AdjustDown(HPDataType* a, int n, int parent) { // 先假设左孩子小 int child parent * 2 1; while (child n) { // 如果右孩子比左孩子小child1 if (child 1 n a[child] a[child 1]) { child; } if (a[child] a[parent]) { Swap(a[child], a[parent]); parent child; child parent * 2 1; } else { break; } } }传入数组、数组大小和要进行调整的结点。使用假设法找出左右子树根节点的较小值如果根节点较小值小于其父节点则进行交换。交换之后将孩子节点看作新的父节点再算出新的父节点的孩子节点重复这一过程直到全部变为堆。2.堆的创建给出一个数组这个数组逻辑上可以看作是一个完全二叉树但还不是一个堆。通过向下调整算法可以将它构建成一个堆。从倒数第一个非叶子结点开始使用向下调整算法一直调整到根节点就可以构建成堆。3.堆的插入先插入一个数到数组的尾上再进行向上调整算法直到满足堆。如果是小堆插入一个元素后和其父节点比较如果新插入的结点小于父节点则交换位置直到二叉树完全满足堆。// 向上调整算法 void AdjustUP(HPDataType* a, int child); // 堆的插入 void HPPush(HP* php, HPDataType x);void AdjustUP(HPDataType* a, int child) { int parent (child - 1) / 2; while (child 0) { if (a[child] a[parent]) { Swap(a[child], a[parent]); child parent; parent (child - 1) / 2; } else { break; } } } void HPPush(HP* php, HPDataType x) { assert(php); if (php-size php-capacity) { int newCapacity php-capacity 0 ? 4 : php-capacity * 2; HPDataType* tmp (HPDataType*)realloc(php-a, newCapacity * sizeof(HPDataType)); if (php NULL) { perror(realloc fail); return; } php-a tmp; php-capacity newCapacity; } php-a[php-size] x; php-size; AdjustUP(php-a, php-size - 1); }4.堆的删除删除堆是删除堆顶的数据。将堆顶的数据和最后一个数据交换再将最后一个数据删除再对新堆顶进行向下调整算法。// 堆的删除 void HPPop(HP* php);void HPPop(HP* php) { assert(php); assert(php-size 0); Swap(php-a[0], php-a[php-size - 1]); php-size--; AdjustDown(php-a, php-size, 0); }5.堆的代码实现完整代码#pragma once #includestdio.h #includeassert.h #includestdlib.h #includestdbool.h typedef int HPDataType; typedef struct Heap { HPDataType* a; int size; int capacity; }HP; void Swap(HPDataType* p1, HPDataType* p2); // 向上调整算法 void AdjustUP(HPDataType* a, int child); // 向下调整算法 void AdjustDown(HPDataType* a, int n, int parent); // 初始化 void HPInit(HP* php); // 销毁 void HPDestroy(HP* php); // 插入 void HPPush(HP* php, HPDataType x); // 删除 void HPPop(HP* php); // 获取堆顶元素 HPDataType HPTop(HP* php); // 判断堆是否为空 bool HPEmpty(HP* php);#define _CRT_SECURE_NO_WARNINGS 1 #includeheap.h void HPInit(HP* php) { assert(php); php-a NULL; php-size php-capacity 0; } void HPDestroy(HP* php) { assert(php); free(php-a); php-a NULL; php-size php-capacity 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; while (child 0) { if (a[child] a[parent]) { Swap(a[child], a[parent]); child parent; parent (child - 1) / 2; } else { break; } } } void HPPush(HP* php, HPDataType x) { assert(php); if (php-size php-capacity) { int newCapacity php-capacity 0 ? 4 : php-capacity * 2; HPDataType* tmp (HPDataType*)realloc(php-a, newCapacity * sizeof(HPDataType)); if (php NULL) { perror(realloc fail); return; } php-a tmp; php-capacity newCapacity; } php-a[php-size] x; php-size; AdjustUP(php-a, php-size - 1); } void AdjustDown(HPDataType* a, int n, int parent) { // 先假设左孩子小 int child parent * 2 1; while (child n) { // 如果右孩子比左孩子小child1 if (child 1 n a[child] a[child 1]) { child; } if (a[child] a[parent]) { Swap(a[child], a[parent]); parent child; child parent * 2 1; } else { break; } } } void HPPop(HP* php) { assert(php); assert(php-size 0); Swap(php-a[0], php-a[php-size - 1]); php-size--; AdjustDown(php-a, php-size, 0); } HPDataType HPTop(HP* php) { assert(php); assert(php-size 0); return php-a[0]; } bool HPEmpty(HP* php) { assert(php); return (php-size 0); }三、堆的应用1.堆排序堆排序即利用堆的思想进行排序分为两个步骤1建堆升序建大堆降序建小堆2利用堆的删除思想进行排序建堆和堆删除都用到了向下调整因此掌握了向下调整就可以完成堆排序。以降序排序为例排序过程先将数组建成小堆再将堆顶数据和最后一个数据交换然后将堆中的数据个数-1即将最后一个元素排除出堆再对堆顶进行向下调整算法直到二叉树符合堆的性质重复这一步骤直到堆中只剩一个元素即为完成了堆排序。2.TOP-K问题TOP-K问题即求数据中前K个最大的元素或最小的元素一般情况下数据量都比较大N个数中找最大或最小的前K个数N远大于K。如果数据量很大排序就不太可能了数据可能无法一次性加载到内存中。最佳的方式就是使用堆。基本思路如下1用数据中前K个元素来建堆前K个最大的元素则建小堆前K个最小的元素则建大堆2用剩余的N-K个元素依次与堆顶元素进行比较不满足则替换堆顶元素。将剩余的N-K个元素全部比较完成后堆中剩余的元素就是前k个最大或最小的元素。void Test() { int a[] { 4,2,8,1,5,6,9,7 }; HP hp; HPInit(hp); for (int i 0; i sizeof(a) / sizeof(a[0]); i) { HPPush(hp, a[i]); } // 找出最小的前k个 int k; scanf(%d, k); while (k--) { printf(%d , HPTop(hp)); HPPop(hp); } }完