基础微网站开发动态,网站彩票投注员做啥的,上海沪琛品牌营销策划有限公司,wordpress响应案例文章目录 1.堆2.C语言实现堆2.1 堆结构与基本操作2.2 其它辅助操作2.3 堆的基本操作2.3.1 插入2.3.2 删除 3. 堆排序4. TopK5. 所有代码 1.堆
堆总是一棵完全二叉树#xff0c;而完全二叉树更适合使用**顺序结构#xff08;数组#xff09;**存储#xff0c;完全二叉树前h… 文章目录 1.堆2.C语言实现堆2.1 堆结构与基本操作2.2 其它辅助操作2.3 堆的基本操作2.3.1 插入2.3.2 删除 3. 堆排序4. TopK5. 所有代码 1.堆
堆总是一棵完全二叉树而完全二叉树更适合使用**顺序结构数组**存储完全二叉树前h-1层是满的最后一层不一定是满的但节点一定连续的。需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 非完全二叉树不适合用数组来存储因为存在空间浪费。而极端的二叉搜索树则会造成更多浪费二叉搜索树即右孩子节点比父节点大左孩子节点比父节点小的树。 使用数组存储二叉树基于父子节点下标间的关系leftchild parent * 2 1rightchild parent * 2 2parent (child - 1) / 2如果打破这种存储关系则数组无法表示二叉树所以数组存储非完全二叉树注定要浪费空间。
将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。最大堆即任意一个父节点都大于等于孩子节点最小堆即任意一个父节点都小于等于孩子节点。
满二叉树实际上也是一棵特殊的完全二叉树树的每一层都是满节点即是满二叉树。满二叉树有这样一个规律第一层的节点数为20第二层节点数为21假设树的高度为h则第h层的节点数为2h-1不难看出是一个等比数列所以满二叉树的节点数量为2h-1。 基于这样一个规律则完全二叉树最多有2h-1个节点最少有2h-1个节点[2h-12h-1]。知道了节点数量也就知道了树的高度h假设N是节点数量N 2h-1则h log2(N) 1N 2h-1则h log2(N1)。
2.C语言实现堆
2.1 堆结构与基本操作
堆结构看起来与顺序表无异毕竟都是数组实现。不一样的是逻辑结构顺序表是线性结构堆是树形结构。堆的基本操作只有插入和删除应用场景有堆排序和TopK前k个最大或最小的数。
#pragma once
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.h// 堆结构
typedef int datatype;
typedef struct Heap {datatype* arr;int size;int capacity;
} Heap;// 其它辅助操作
void HeapInit(Heap* heap);
void HeapDestroy(Heap* heap);
datatype HeapTop(Heap* heap); // 取堆顶元素
size_t HeapSize(Heap* heap);
bool HeapEmpty(Heap* heap);// logn
void HeapPush(Heap* heap, datatype val);
void HeapPop(Heap* heap); // 删除堆顶元素
// 插入或删除时堆向上、向下调整
void Swap(datatype* x, datatype* y);
void AdjustUp(datatype* arr, int child);
void AdjustDown(datatype* arr, int size, int parent);// 堆排序 nlogn、求TopK nlogk
void HeapSort(datatype* arr, int size);
void PrintTopK(const char* file, int k);2.2 其它辅助操作
void HeapInit(Heap* heap) {assert(heap);heap-arr NULL;heap-size heap-capacity 0;
}void HeapDestroy(Heap* heap) {assert(heap);free(heap-arr);heap-arr NULL;heap-size heap-capacity 0;
}datatype HeapTop(Heap* heap) {assert(heap heap-arr heap-size 0);return heap-arr[0];
}size_t HeapSize(Heap* heap) {assert(heap);return heap-size;
}bool HeapEmpty(Heap* heap) {assert(heap);return heap-size 0;
}
2.3 堆的基本操作
2.3.1 插入
直接往数组插入数据然后再向上调整即可。以构建最小堆举例只要插入的数据比父节点小就与父节点交换重复这个操作直到不能再做交换。
void HeapPush(Heap* heap, datatype val) {assert(heap);if (heap-size heap-capacity) { // 空间不够时扩容heap-capacity heap-capacity 0 ? 10 : heap-capacity * 2;datatype* tmp realloc(heap-arr, sizeof(datatype) * heap-capacity);if (tmp NULL) {perror(HeapPush malloc failed.);exit(-1);}heap-arr tmp;}// 插入heap-arr[heap-size] val;AdjustUp(heap-arr, heap-size - 1);
}
void Swap(datatype* x, datatype* y) {int tmp *x;*x *y;*y tmp;
}
// logn
void AdjustUp(datatype* arr, int child) {int parent (child - 1) / 2;while (child 0 arr[child] arr[parent]) {Swap(arr[child], arr[parent]); // upchild parent;parent (child - 1) / 2;}
}如果将while循环的条件arr[child] arr[parent]改成大于arr[child] arr[parent]则是调整构建最大堆。
Heap heap;
HeapInit(heap);
// 建堆 nlogn
HeapPush(heap, 67864);
HeapPush(heap, 7432);
HeapPush(heap, 854312);
HeapPush(heap, 909876);
HeapPush(heap, 8765);
HeapPush(heap, 2345678);
HeapPush(heap, 2563);
HeapPush(heap, 12676);
HeapPush(heap, 6543);
HeapPush(heap, 2167);
for (int i 0; i heap.size; i) {printf(%d , heap.arr[i]);
}
HeapDestroy(heap);2.3.2 删除
删除堆元素只能删除堆顶元素这是合理的规定其它诸如任意删除、删除最后一个元素的操作对堆而言都是没有意义的。
如果是直接删除堆顶元素数组剩下的元素不再构成堆所以不能这么做。还是以最小堆为例1标准的实现是将堆顶元素与数组最后一个元素进行交换即最小的数与较大的数交换接着删除最后一个元素然后再向下调整目的是将堆顶元素往下沉重新构建最小堆2向下调整的思路从左右孩子节点中选出最小的这个孩子节点比父节点小就做交换重复这个操作。
void HeapPop(Heap* heap) {assert(heap heap-arr heap-size 0);Swap(heap-arr[0], heap-arr[--heap-size]);AdjustDown(heap-arr, heap-size, 0);
}
void Swap(datatype* x, datatype* y) {int tmp *x;*x *y;*y tmp;
}
// logn
void AdjustDown(datatype* arr, int size, int parent) {int child parent * 2 1; // left or right child child 1 size arr[child 1] arr[child]? child : chi// childparent调整为小堆childparent调整为大堆 while (child size arr[child] arr[parent]) {Swap(arr[child], arr[parent]); // downparent child;child parent * 2 1; // left or rightchild child1 size arr[child1] arr[child]? child : child;}
}如果将arr[child 1] arr[child]改成arr[child 1] arr[child]以及while循环的条件arr[child] arr[parent]改成大于arr[child] arr[parent]则是调整构建最大堆。
Heap heap;
HeapInit(heap);
// 建堆 nlogn
HeapPush(heap, 67864);
HeapPush(heap, 7432);
HeapPush(heap, 854312);
HeapPush(heap, 909876);
HeapPush(heap, 8765);
HeapPush(heap, 2345678);
HeapPush(heap, 2563);
HeapPush(heap, 12676);
HeapPush(heap, 6543);
HeapPush(heap, 2167);
while (!HeapEmpty(heap)) {printf(%d , HeapTop(heap));HeapPop(heap);
}
HeapDestroy(heap);这其实相当于排了个序时间复杂度为nlogn。不过由于还有插入操作的时间复杂度nlogn所以整体时间复杂度为2n*2logn。
另外这也能解决TopK问题
int k 3;
while (k--) {printf(%d , HeapTop(heap));HeapPop(heap);
}3. 堆排序
前面借助堆基本操作Top和Pop也能做到堆排序不过却比较麻烦因为需要实现堆的基本操作。这里所指的堆排序是指直接将数组构建成堆然后排序不包含建堆的时间则堆排序的时间复杂度为nlogn。
// 排升序则构建大堆排降序则构建小堆
void HeapSort(datatype* arr, int size) {// 建堆 O(nlogn) //for (int i 1; i size; i) {// AdjustUp(arr, i); //}// 建堆 O(n) 并非是nlognfor (int i (size - 1 - 1) / 2; i 0; --i) {AdjustDown(arr, size, i);}// 排序 O(nlogn)for (int end size - 1; end 0; --end) {Swap(arr[0], arr[end]);AdjustDown(arr, end, 0);}
}利用向下调整建堆的时间复杂度为O(n)的原因是最后一层不需要向下调整直接从倒数第二层开始向下调整这节省了很多时间复杂度毕竟最后一层的节点占了堆节点总数一半。每一层的节点数量越多向下调整次数越少每一层的节点数量越少向下调整的次数才越多。
而利用向上调整构建堆从最后一层的节点往上则会耗费较多时间复杂度因为最后一层也需要向上调整。
4. TopK
如果数据量太大比如一千万个数据以int来算则是四千万字节差不多相当于40G内存如果还是按以前那样将所有数据插入堆中求TopK显然是不可能的。
void PrintTopK(const char* file, int k) {// 文件FILE* fr fopen(file, r);if (fr NULL) {perror(PrintTopK fopen failed.);exit(-1);}// 大小为k的堆datatype* minheap (datatype*)malloc(sizeof(datatype) * k);if (minheap NULL) {perror(PrintTopK malloc failed.);exit(-1);}// 从文件读取前k个建小堆for (int i 0; i k; i) {fscanf(fr, %d, minheap[i]);AdjustUp(minheap, i); // childparent}// 从文件挨个读取寻找TopKint val 0;while (fscanf(fr, %d, val) ! EOF) {if (val *minheap) {*minheap val; // 大的往下沉 childparentAdjustDown(minheap, k, 0); }}// 打印TopKfor (int i 0; i k; i) {printf(%d , minheap[i]);}printf(\n);free(minheap);minheap NULL;fclose(fr);
}5. 所有代码
#pragma once#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.h// 堆结构
typedef int datatype;
typedef struct Heap {datatype* arr;int size;int capacity;
} Heap;void HeapInit(Heap* heap);
void HeapDestroy(Heap* heap);void HeapPush(Heap* heap, datatype val);
void HeapPop(Heap* heap);
// 插入或删除时堆向上、向下调整
void Swap(datatype* x, datatype* y);
void AdjustUp(datatype* arr, int child);
void AdjustDown(datatype* arr, int size, int parent);datatype HeapTop(Heap* heap);
size_t HeapSize(Heap* heap);
bool HeapEmpty(Heap* heap);// 堆排序、求TopK
void HeapSort(datatype* arr, int size);
void PrintTopK(const char* file, int k);#define _CRT_SECURE_NO_WARNINGS 1#include Heap.hvoid HeapInit(Heap* heap) {assert(heap);heap-arr NULL;heap-size heap-capacity 0;
}void HeapDestroy(Heap* heap) {assert(heap);free(heap-arr);heap-arr NULL;heap-size heap-capacity 0;
}void HeapPush(Heap* heap, datatype val) {assert(heap);if (heap-size heap-capacity) {heap-capacity heap-capacity 0 ? 10 : heap-capacity * 2;datatype* tmp realloc(heap-arr, sizeof(datatype) * heap-capacity);if (tmp NULL) {perror(HeapPush malloc failed.);exit(-1);}heap-arr tmp;}heap-arr[heap-size] val;AdjustUp(heap-arr, heap-size - 1);
}void HeapPop(Heap* heap) {assert(heap heap-arr heap-size 0);Swap(heap-arr[0], heap-arr[--heap-size]);AdjustDown(heap-arr, heap-size, 0);
}datatype HeapTop(Heap* heap) {assert(heap heap-arr heap-size 0);return heap-arr[0];
}size_t HeapSize(Heap* heap) {assert(heap);return heap-size;
}bool HeapEmpty(Heap* heap) {assert(heap);return heap-size 0;
}void Swap(datatype* x, datatype* y) {int tmp *x;*x *y;*y tmp;
}void AdjustUp(datatype* arr, int child) {int parent (child - 1) / 2;while (child 0 arr[child] arr[parent]) {Swap(arr[child], arr[parent]); // upchild parent;parent (child - 1) / 2;}
}void AdjustDown(datatype* arr, int size, int parent) {int child parent * 2 1; //child1为右孩子节点child child 1 size arr[child 1] arr[child]? child : child;// childparent调整为小堆childparent调整为大堆 while (child size arr[child] arr[parent]) {Swap(arr[child], arr[parent]); // downparent child;child parent * 2 1; // left or rightchild child1 size arr[child1] arr[child]? child : child;}
}// 升序构建大堆降序构建小堆
void HeapSort(datatype* arr, int size) {// 建堆 O(nlogn) //for (int i 1; i size; i) {// AdjustUp(arr, i); //}// 建堆 O(n) for (int i (size - 1 - 1) / 2; i 0; --i) {AdjustDown(arr, size, i);}// 排序 O(nlogn)for (int end size - 1; end 0; --end) {Swap(arr[0], arr[end]);AdjustDown(arr, end, 0);}
}void PrintTopK(const char* file, int k) {// 文件FILE* fr fopen(file, r);if (fr NULL) {perror(PrintTopK fopen failed.);exit(-1);}// 大小为k的堆datatype* minheap (datatype*)malloc(sizeof(datatype) * k);if (minheap NULL) {perror(PrintTopK malloc failed.);exit(-1);}// 从文件读取前k个建小堆for (int i 0; i k; i) {fscanf(fr, %d, minheap[i]);AdjustUp(minheap, i); // childparent}// 从文件挨个读取寻找TopKint val 0;while (fscanf(fr, %d, val) ! EOF) {if (val *minheap) {*minheap val; // 大的往下沉 childparentAdjustDown(minheap, k, 0); }}// 打印TopKfor (int i 0; i k; i) {printf(%d , minheap[i]);}printf(\n);free(minheap);minheap NULL;fclose(fr);
}#define _CRT_SECURE_NO_WARNINGS #include Heap.h
#include time.hstatic void CreateNData();int main() {//Heap heap;//HeapInit(heap); 建堆 nlogn//HeapPush(heap, 67864);//HeapPush(heap, 7432);//HeapPush(heap, 854312);//HeapPush(heap, 909876);//HeapPush(heap, 8765);//HeapPush(heap, 2345678);//HeapPush(heap, 2563);//HeapPush(heap, 12676);//HeapPush(heap, 6543);//HeapPush(heap, 2167);//printf(%zd\n, HeapSize(heap));//for (int i 0; i heap.size; i) {// printf(%d , heap.arr[i]);//}//printf(\n);// top k//int k 3; //while (k--) {// printf(%d , HeapTop(heap));// HeapPop(heap);//}//printf(\n);// Push nlogn 排序 nlogn O(2nlogn)//while (!HeapEmpty(heap)) {// printf(%d , HeapTop(heap));// HeapPop(heap);//}//HeapDestroy(heap);//printf(\n);// 堆排序//int arr[] { 67864,7432,854312,909876,8765,2345678,2563,12676,6543,2167 };//HeapSort(arr, sizeof arr / sizeof arr[0]);//for (int i 0; i sizeof arr / sizeof arr[0]; i) {// printf(%d , arr[i]);//}// 大量数据下的TopK//CreateNData(); PrintTopK(data.txt, 6);return 0;
}static void CreateNData() {int n 100000;srand((unsigned int)time(0));FILE* fw fopen(data.txt, w);if (fw NULL) {perror(CreateNData fopen failed.);exit(-1);}for (int i 0; i n; i) {fprintf(fw, %d\n, rand() % n);}fclose(fw);
}
