目录一、堆的概念和性质大堆小堆二、堆的实现2.1 堆的初始化2.2 堆的销毁2.3 堆的插入向上调整算法2.4 删除堆顶元素向下调整算法2.5 堆的删除2.6 堆的判空2.7 求堆中元素个数三、堆的应用3.1 向下调整算法建堆3.2 向上调整算法建堆3.3 堆排序3.4 TOP-K问题四、总结与反思一、堆的概念和性质大堆小堆堆是一个数据结构不是操作系统上的堆堆的原理就是完全二叉树只不过堆需要满足小堆和大堆才是堆结构,它底层是通过数组存储方式进行存储的物理结构是线性的但是逻辑结构不是线性的。大堆是由大到小的顺序开始建堆而小堆是从小到到进行排列堆有以下性质1.堆中某个结点的值总是不大于大堆或不小于小堆父结点2.堆总是一颗完全二叉树。二叉树性质对于具有n个结点的完全二叉树如果按照从上到下从左到右顺序从0开始为根结点对于序列为i的节点1.i0i位置节点的双亲序列为i-1/2i0为根结点无双亲结点。2.若2i1n则左孩子的序列为2i12i2n。右孩子的序列为2i2。二、堆的实现2.1 堆的初始化初始化时先定义堆结构//堆结构 typedef int HPDataType; typedef struct Heap { HPDataType* arr;//数组存储 int size;//有效元素 int capacity;//空间 }Heap;初始化//初始化 void HeapInit(Heap* php) { php-arr NULL; php-capacity php-size 0; }2.2 堆的销毁//销毁 void HeapDestroy(Heap* php) { assert(php); php-arr NULL; php-capacity php-size 0; }2.3 堆的插入向上调整算法//堆的插入(向上调整算法) void HeapPush(Heap* php, HPDataType x) { //空间不够 if (php-capacity php-size) { int newCapacity php-capacity 0 ? 4 : 2 * php-capacity; HPDataType* tmp (HPDataType*)realloc(php-arr, newCapacity * sizeof(HPDataType)); if (tmp NULL) { perror(realloc); exit(1); } php-arr tmp; php-capacity newCapacity; } php-arr[php-size] x; //向上建堆 AdjustUp(php-arr,php-size); php-size; }这里需要应该向上调整算法插入完后调整。堆的插入我们用图来描述一下纠正一下parent (child-1)/2。通过这个图不难发现当child0时跳出循环childparent,parent(child-1)/2然后当我们发现插入的值比parent大时向上兑换大堆向上调整算法代码实现就很简单了//交换 void Swap(HPDataType* change1, HPDataType* change2) { HPDataType tmp *change1; *change1 *change2; *change2 tmp; } //向上调整算法 void AdjustUp(HPDataType* 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; } } }2.4 删除堆顶元素向下调整算法//删堆顶 void HeapPop(Heap* php) { assert(!HeapEmpty); //堆顶和最后一个叶子结点交换 Swap(php-arr[0], php-arr[php-size - 1]); php-size--; //向下调整 AdjustDown(php-arr, 0, php-size); }删除堆顶数据时需要堆顶和最后一个叶子结点交换然后size减减然后进行向下调整算法调整堆。删堆顶可以用这个gif图来表示通过这个gif图可知这个向下调整算法需要对比左右孩子哪个大小才能和parent进行比较并将大的孩子与parent进行比较比孩子小则要调整。//向下调整算法 void AdjustDown(HPDataType* arr, int parent, int size) { int child parent * 2 1;//左孩子 while (child size) { //比较左孩子和右孩子哪个大 //大堆 //小堆 if (child 1 size arr[child] arr[child 1]) { child; } //小堆 //大堆 if (arr[child] arr[parent]) { Swap(arr[child], arr[parent]); parent child; child parent * 2 1; } else { break; } } }2.5 堆的删除//取堆顶数据 HPDataType HeapTop(Heap* php) { assert(!HeapEmpty(php)); return php-size[0]; }2.6 堆的判空//判空 bool HeapEmpty(Heap* php) { assert(php); return php-size 0; }2.7 求堆中元素个数//堆中元素个数 int HeapSize(Heap* php) { assert(php); return php-size; }三、堆的应用3.1 向下调整算法建堆利用堆的思想来给数组建堆//向下调整算法 void AdjustDown(HPDataType* arr, int parent, int size) { int child parent * 2 1;//左孩子 while (child size) { //比较左孩子和右孩子哪个大 //大堆 //小堆 if (child 1 size arr[child] arr[child 1]) { child; } if (arr[child] arr[parent]) { Swap(arr[child], arr[parent]); parent child; child parent * 2 1; } else { break; } } } void CreateHeap(int* arr, int size) { //向下建堆 for (int i (size - 1 - 1) / 2; i 0; i--) { //通过遍历父节点来建堆 AdjustDown(arr, i, size);//大堆 } for (int j 0; j size; j) { printf(%d , arr[j]); } }3.2 向上调整算法建堆void CreateHeap(int* arr, int size) { //向上建堆 for (int i size; i 0; i--) { //遍历子结点建堆 AdjustUp(arr, i); } for (int j 0; j size; j) { printf(%d , arr[j]); } }3.3 堆排序在进行堆排序之前我们先讨论两个建堆算法的时间复杂度这里可得向下排序算法时间复杂度要小所以我们在用堆排序时这里是用的向下建堆的。void HeapSort(int* arr, int size) { //大堆---升序 //小堆---降序 for(int i size-1; i 0;i--) { Swap(arr[0], arr[i]);//堆顶和尾叶子结点交换 AdjustDown(arr, 0,i);//调整为大堆 } //打印顺序 printf(堆排序后:); for (int j 0; j size; j) { printf(%d , arr[j]); } printf(\n); } void CreateHeap(int* arr, int size) { //向下建堆 for (int i (size - 1 - 1) / 2; i 0; i--) { //通过遍历父节点来建堆 AdjustDown(arr, i, size);//大堆 } //向上建堆 //for (int i size; i 0; i--) //{ // //通过遍历子结点来建堆 // AdjustUp(arr, i); //} printf(堆排序前); for (int j 0; j size; j) { printf(%d , arr[j]); } printf(\n); } int main() { int arr[] { 10,21,2,9,20,13,12,58 }; int size sizeof(arr) / sizeof(arr[0]); CreateHeap(arr,size); HeapSort(arr, size); return 0; }3.4 TOP-K问题对与这种问题我们一般都是将所以数据都存储到数组中然后进行堆排序。但是当数据非常大时加上内存有限的条件下这种方法不行。那我们该如何解决当然这里还是离不开堆排序我们可以吧前k个数据存储到数组中然后进行建堆并堆排序取堆顶和升序n-k个数据进行比较比较大小进行调堆获得最k个最值。//Top——K问题 void PrintTok(int k) { //申请空间 int* arr (int*)malloc(sizeof(int) * k); if (arr NULL) { perror(malloc); exit(2); } //打开空间 FILE* file fopen(data.txt, r); if (file NULL) { perror(fopen fail); exit(3); } //将k个数据移入数组中 for (int i 0; i k; i) { fscanf(file, %d, arr[i]); } //向下建堆 for (int j (k - 1 - 1) / 2; j 0; j--) { AdjustDown(arr, j, k);//大堆 } //将n-k个数据与堆顶进行比较 //堆顶 n-k内的数据则交换再向下调整 int x 0; while (fscanf(file, %d, x) ! EOF) { if (arr[0] x) { arr[0] x; AdjustDown(arr, 0, k); } } for(int m 0;m k;m) { printf(%d , arr[m]); } printf(\n); free(arr); arr NULL; //关闭文件 fclose(file); } //写数据到文件中 void CreateNData() { //int n 100000; //srand((unsigned int)time(0)); ////打开文件 //const char* txt data.txt; //FILE* file fopen(txt, w); //if (file NULL) //{ // perror(fopen fail); // exit(1); //} ////存储到data.txt //for (int i 0; i n-10; i) //{ // fprintf(file, %d\n, rand() % 100000); //} //for (int j n - 10; j n; j) //{ // fprintf(file, %d\n, j % 10000); //} // ////关闭文件 //fclose(file); // int n 100000; srand((unsigned int)time(0)); // 设置种子 const char* file data.txt; FILE* fin fopen(file, w); if (fin NULL) { perror(fopen fail); exit(1); } // 生成普通随机数 for (size_t i 0; i n - 10; i) { int x rand() % 100000; fprintf(fin, %d\n, x); } // 添加10个明显的大值100000以上 for (int i 0; i 10; i) { fprintf(fin, %d\n, 100000 - i); } fclose(fin); } int main() { CreateNData(); int n 0; printf(输入k为:); scanf(%d, n); //大堆---前k个最小 //小堆---前k个最大 PrintTok(n); return 0; }四、总结与反思堆在排序中优势很好时间复杂度就为O(nlogn)但是无论如何都避免不了和冒泡排序一样将所有的都遍历了一边在解决TOP——K问题上门还是有很大用处的可以避免在操作系统上申请空间在提高性能方面有很大作用。而相对于向上调整算法向下调整算法建堆的时间复杂度要低能够优化算法提高编译效率。这个建堆的思想能够为我们收获最大值小堆和最小值大堆为我们优化排序提供了一个好方法。