jquery 网站模板wordpress客户端5.8

当前位置： 首页 > news >正文

jquery 网站模板,wordpress客户端5.8,免费建网站,亿玛酷网站建设目录 一、堆的概念及结构 二、堆的实现 1.堆的定义 2堆的初始化 3堆的插入 ​编辑 4.堆的删除 5堆的其他操作 6代码合集 三、堆的应用 #xff08;一#xff09;堆排序#xff08;重点#xff09; #xff08;二#xff09;TOP-K问题 一、堆的概念及结构 堆的…目录 一、堆的概念及结构 二、堆的实现 1.堆的定义 2堆的初始化 3堆的插入 ​编辑 4.堆的删除 5堆的其他操作 6代码合集 三、堆的应用 一堆排序重点 二TOP-K问题 一、堆的概念及结构 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树但实现起来是线性表。 二、堆的实现 1.堆的定义 //大堆 typedef int HPDataType; typedef struct Heap {HPDataType* a;int size;int capacity; }HP; 2堆的初始化 //堆的初始化 void HeapInit(HP* php) {assert(php);php-a (HPDataType*)malloc(sizeof(HPDataType)4);if (php-a NULL){perror(malloc fail);return;}php-size 0;php-capacity 4; } 3堆的插入 //从孩子的位置向上调整函数 void AdjustUp(HPDataType a, int child)//child是向上调整数的下标 {int parent (child - 1) / 2;while (child0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}} } //堆的插入 void HeapPush(HP* php, HPDataType x) {assert(php);if (php-size php-capacity){HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType) * php-capacity*2);if (php-a NULL){perror(malloc fail);return;}// 将旧数据拷贝到新内存中for (int i 0; i php-size; i){tmp[i] php-a[i];}free(php-a);php-a tmp;php-capacity * 2;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);//刚才size了所以向上调整的孩子的位置是size-1 } 4.堆的删除 删除堆顶用处可用来排序选出前几名 删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 难点 向下比怎么比下面哪个儿子大就和谁比 怎么判断已经到叶子节点了计算该节点的孩子节点有没有超出范围
//向下调整 void AdjustDown(HPDataType* a, int n,int parent) {int child parent * 2 1;//先默认左孩子大while (child n){//选出左右孩子中大的那一个 右孩子和左孩子的关系大一if (child1n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}} } //堆的删除 void HeapPop(HP* php) {assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);//交换堆顶和最后一个数php-size–;AdjustDown(php-a, php-size,0); } 如果想要取前k个那么修改如下  5堆的其他操作 //显示堆顶元素 HPDataType HeapTop(HP* php) {assert(php);return php-a[0]; } //判断堆是否为空 bool HeapEmpty(HP* php) {assert(php);return php-size0; } //显示堆的大小 int HeapSize(HP* php) {assert(php);return php-size; } //销毁 void HeapDestroy(HP* php) {assert(php);free(php-a);php-a NULL;php-size php-capacity 0; }6代码合集 Heap.h #pragma once #includestdio.h #includeassert.h #includestdlib.h #includestdbool.h //大堆 typedef int HPDataType; typedef struct Heap {HPDataType* a;int size;int capacity; }HP; //堆的初始化 void HeapInit(HP* php); //堆的插入 void HeapPush(HP* php, HPDataType x); //堆的删除 void HeapPop(HP* php); //显示堆顶元素 HPDataType HeapTop(HP* php); //判断堆是否为空 bool HeapEmpty(HP* php); //显示堆的大小 int HeapSize(HP* php); //销毁 void HeapDestroy(HP* php); //从孩子的位置向上调整函数 void AdjustUp(HPDataType* a, int child); //向下调整 void AdjustDown(HPDataType* a, int n, int parent); Heap.c #includeHeap.h //堆的初始化 void HeapInit(HP* php) {assert(php);php-a (HPDataType*)malloc(sizeof(HPDataType)4);if (php-a NULL){perror(malloc fail);return;}php-size 0;php-capacity 4; } void Swap(HPDataType p1, HPDataType* p2) {HPDataType temp *p1;*p1 *p2;p2 temp; } //从孩子的位置向上调整函数 void AdjustUp(HPDataType a, int child)//child是向上调整数的下标 {int parent (child - 1) / 2;while (child0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}} } //堆的插入 void HeapPush(HP* php, HPDataType x) {assert(php);if (php-size php-capacity){HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType) * php-capacity*2);if (php-a NULL){perror(malloc fail);return;}// 将旧数据拷贝到新内存中for (int i 0; i php-size; i){tmp[i] php-a[i];}free(php-a);php-a tmp;php-capacity * 2;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);//刚才size了所以向上调整的孩子的位置是size-1 } //向下调整 void AdjustDown(HPDataType* a, int n,int parent) {int child parent * 2 1;//先默认左孩子大while (child n){//选出左右孩子中大的那一个 右孩子和左孩子的关系大一if (child1n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}} } //堆的删除 void HeapPop(HP* php) {assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);//交换堆顶和最后一个数php-size–;AdjustDown(php-a, php-size,0); } //显示堆顶元素 HPDataType HeapTop(HP* php) {assert(php);return php-a[0]; } //判断堆是否为空 bool HeapEmpty(HP* php) {assert(php);return php-size0; } //显示堆的大小 int HeapSize(HP* php) {assert(php);return php-size; } //销毁 void HeapDestroy(HP* php) {assert(php);free(php-a);php-a NULL;php-size php-capacity 0; }test.c #includeHeap.h int main() {HP hp;HeapInit(hp);HeapPush(hp, 4);HeapPush(hp, 18);HeapPush(hp, 42);HeapPush(hp, 12);HeapPush(hp, 2);HeapPush(hp, 3);int k 0;scanf_s(%d, k);while (!HeapEmpty(hp)k–){printf(%d , HeapTop(hp));HeapPop(hp);//和栈非常相似想把老二取出来就得把老大干掉}printf(\n);return 0; } 三、堆的应用 一堆排序重点 ①. 建堆 升序建大堆 降序建小堆 建堆方式 向上调整建堆模拟的是插入数据的过程 //排升序建大堆 void HeapSort(int* a, int n) {//建大堆for (int i 1; i n; i){AdjustUp(a, i);} }向下调整建堆左右子树必须是大堆或小堆插入之前得是堆 void HeapSort(int* a, int n) {//向下调整建堆for (int i (n - 1 - 1) / 2; i 0;–i)//先找到最后一个非叶子结点即上图的6 n-1是最后一个数据的下标再-1除以2就是父节点{AdjustDown(a, n, i);} } 注向下建堆的效率ON比向上建堆的效率ONlogN高 数学证明如下 ②. 利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。 代码实现 #includestdlib.hvoid Swap(HPDataType p1, HPDataType* p2) {HPDataType temp *p1;*p1 *p2;p2 temp; } //从孩子的位置向上调整函数 void AdjustUp(HPDataType a, int child)//child是向上调整数的下标 {int parent (child - 1) / 2;while (child0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}} }//向下调整 void AdjustDown(HPDataType* a, int n,int parent) {int child parent * 2 1;//先默认左孩子大while (child n){//选出左右孩子中大的那一个 右孩子和左孩子的关系大一if (child1n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}} }//O(nlogn) //排升序建大堆 void HeapSort(int a, int n) {//向下调整建堆 for (int i (n - 1 - 1) / 2; i 0;–i)//n-1是最后一个数据的下标再-1除以2就是父节点 {AdjustDown(a, n, i); }int end n - 1;while (end0){Swap(a[end], a[0]);AdjustDown(a, end, 0);–end;} } int main() {int a[10] { 2,1,5,7,6,8,0,9,3 };HeapSort(a, 9);return 0; } ③堆排序的时间复杂度 所以如果用来排序的话无论是向上调整还是向下调整建堆总的时间复杂度都是O(NlogN) 二TOP-K问题 TOP-K 问题即求数据结合中前 K 个最大的元素或者最小的元素一般情况下数据量都比较大 。 比如专业前 10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。 对于 Top-K 问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了 ( 可能 数据都不能一下子全部加载到内存中 ) 。最佳的方式就是用堆来解决基本思路如下 1. 用数据集合中前 K 个元素来建堆 前 k 个最大的元素则建小堆 前 k 个最小的元素则建大堆(和堆排序有点反过来的意思) 2. 用剩余的 N-K 个元素依次与堆顶元素来比较不满足则替换堆顶元素 将剩余 N-K 个元素依次与堆顶元素比完之后堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素 #define _CRT_SECURE_NO_WARNINGS 1 #includeHeap.h void PrintTopK(const char file, int k) {// 1. 建堆–用a中前k个元素建小堆int* topk (int*)malloc(sizeof(int) * k);assert(topk);//读文件FILE* fout fopen(file, r);if (fout NULL){perror(fopen error);return;}//读出前K个数建堆for (int i 0; i k; i){fscanf(fout, %d, topk[i]);}//向下调整建堆for (int i (k - 1 - 1) / 2; i 0; –i){AdjustDown(topk, k, i);}// 2. 将剩余n-k个元素依次与堆顶元素交换不满则则替换int val 0;int ret fscanf(fout, %d, val);while (ret ! EOF){if (val topk[0])//如果新元素大于堆顶元素那么替换堆顶元素{topk[0] val;AdjustDown(topk, k, 0);}ret fscanf(fout, %d, val);}//打印这个数组for (int i 0; i k; i){printf(%d , topk[i]);}printf(\n);free(topk);fclose(fout); } void TestTopk() {//为了测试而造数据int n 10000;srand(time(0));const char* file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fopen error);return;}for (size_t i 0; i n; i){int x rand() % 10000;fprintf(fin, %d\n, x);}fclose(fin);PrintTopK(file,10); } int main() {TestTopk();return 0; } 注意这里是建小堆AdjustDown里面需要调一下之前是建大堆用的AdjustDown