能源建设投资有限公司网站,阿里巴巴运营工资大概多少,wordpress竞争,黄浦做网站公司个人主页#xff1a;点我进入主页 专栏分类#xff1a;C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 欢迎大家点赞#xff0c;评论#xff0c;收藏。 一起努力 目录 1.前言
2.堆排序
2.1降序排序
2.2时间复杂… 个人主页点我进入主页 专栏分类C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 数据结构初阶 欢迎大家点赞评论收藏。 一起努力 目录 1.前言
2.堆排序
2.1降序排序
2.2时间复杂度
3.Top-k问题
4.总结 1.前言 在上一篇文章中我们主要讲解了关于大堆和小堆的代码实现今天我们主要讲解关于堆排序以及堆排序的时间复杂度我们会讲解关于经典的Top-k问题进行讲解其中我会伪造一些数据来展示今天的内容比上次的内容更加的爽更有挑战性其中的奥妙真的无法用语言来形容接下来就让我们感受一下吧。
2.堆排序 我们对数组进行降序排序我们使用堆排序在这里由于升序和降序的思想基本一致只需要修改一些符号即可完成转化所以我们只讲关于降序的内容。
2.1降序排序 在上次的内容中我们使用向上调整来创建堆我们是创建小堆还是大堆呢我们想让数据进行降序如果我们使用大堆的话堆的第一个数是最大的我们取出来之后堆的顺序就乱了我们需要重新进行大堆排序那么我们的时间复杂度为O(n^2*logn),这比我们的冒泡排序还要慢所以大堆是不可以的所以我们选择小堆排序我们这次依旧使用想上调整详细代码如下
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includeassert.h
void Swap(int* num1, int* num2)
{int temp *num1;*num1 *num2;*num2 temp;
}
void print(int* arr, int size)
{for (int i 0; i size; i)printf(%d , arr[i]);
}
void AdJustUp(int* arr, int sz,int size)
{assert(arr);int child sz, parent (child - 1) / 2;while (child0){if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}
void AdJustDown(int* arr, int i, int size)
{assert(arr);int parent i, child 2 * parent 1;while (childsize){if (child 1 size arr[child] arr[child 1]){child;}if (arr[parent] arr[child]){Swap(arr[parent], arr[child]);parent child;child 2 * parent 1;}elsebreak;}
}
void HeapSort(int* arr, int n)
{assert(arr);for (int i 0; i n; i){AdJustUp(arr, i, n);}for (int i 0; i n-1; i){Swap(arr[0], arr[n - 1 - i]);AdJustDown(arr, 0, n - 1 - i);}}
int main()
{int arr[10];int n 10;for (int i 0; i n; i){arr[i] i;}HeapSort(arr,n);print(arr, n);return 0;
}
我们的运行结构如下 事实上我们这不是我们的堆排序真正的堆排序在第一次创建小堆时代码为 for (int i (n - 1 - 1) / 2; i 0; i--){AdJustDown(arr, 0, n - 1 - i);}
向下调整为什么可以实现呢我们知道向下调整是左边和右边都是小堆然后根节点是新插入的我们就可以利用向下调整进行排序那我们在最后一个节点的父节点进行向下调整让他们都成为小堆这样我们就可以完成小堆的创建。那为什么采用这种形式呢仅仅是因为代码少吗事实上这与我们的时间复杂度有关。
2.2时间复杂度 我们看利用向上调整建立小堆的时间复杂度我们第k层有2^(k-1)个节点每个节点需要向上调整k-1次共调整(k-1)*2^(k-1)次第k-1层有2^(k-2)每个节点需要调整k-2次共调整(k-2)*2^(k-2)……第二层有2^1个节点每个节点需要调整1次第一层有2^0个节需要调整0次共需要调整T(k)0*2^01*2^1……(k-2)*2^(k-2)(k-1)*2^(k-1),我们化简可以得到T(k)(k-2)2^k2;其中klogN,所以T(k)NlogN;但是我们采用向下调整我们第k层有我们第k层有2^(k-1)个节点每个节点需要向上调整0次共调整0*2^(k-1)次第k-1层有2^(k-2)每个节点需要调整1次共调整1*2^(k-2)……第二层有2^1个节点每个节点需要调整k-2次第一层有2^0个节需要调整k-1次,共需要调整T(k)(k-1)*2^0(k-2)*2^1……1*2^(k-2)0*2^(k-1),我们化简得到T(k)2^k-k-1其中klogN,故T(k)N-logN;可以看到向下调整建立堆时间复杂度低所以我们选择向下调整这大大减少了我们的运算时间。
3.Top-k问题 有一个问题是我们在一组数中(共N个数)找到最小的k个数其中N远大于k让我们找到前k个数当数据很小的时候我们利用堆排序进行查找很容易但是当数据量特别大的时候我们就很难实现因为数据占用的内存太大了例如我们要在1百亿个数据中找到前10个最小的数100万个整形数据相当于占用37GB,这样我们就很难处理这时候就出现了我们的Top-k问题我们是如何解决这个问题呢这时候我们由于需要找最小的前10个数据我们创建一个大堆然后输入一个数据就将堆顶元素替换然后再向下调整这样就可以找到最小的10个数据我们创建100万个数据进行模拟我们的代码如下
我们将数据放在文件中生成data.txt文件
#includestdio.h
int main()
{FILE* pf fopen(data.txt, w);if (pf NULL){perror(fopen fail);return 1;}for (int i 0; i 1000000; i){fprintf(pf,%d\n, i);}fclose(pf);pf NULL;return 0;
}
修改其中的10个数据让他成为我们的结果然后进行下一步找到这k个数
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
typedef int MyHeapData;
typedef struct Heap {MyHeapData* data;int size;int capacity;
}Heap;
void HeapInit(Heap* php)
{assert(php);php-data (MyHeapData*)malloc(sizeof(MyHeapData)*10);php-size 0;
}
void Swap(int* num1, int* num2)
{int temp *num1;*num1 *num2;*num2 temp;
}
void AdJustDown(int* arr, int n, int i)
{assert(arr);int parent 0, child 2 * parent 1;while (childn){if (child1narr[child] arr[child 1]){child;}if (arr[parent] arr[child]){Swap(arr[parent], arr[child]);parent child;child parent * 2 1;}elsebreak;}
}
void AdJustUp(MyHeapData* arr, int size)
{assert(arr);int child size - 1, parent (child - 1) / 2;while (child 0){if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}elsebreak;}
}
int main()
{//FILE* pf fopen(data.txt, w);//if (pf NULL)//{// perror(fopen fail);// return 1;//}//for (int i 0; i 1000000; i)//{// fprintf(pf,%d\n, i);//}//fclose(pf);//pf NULL;FILE* pf fopen(data.txt, r);if (pf NULL){perror(fopen fail);return 1;}int data;int i;Heap ph ;HeapInit(ph);for (i 0; i 10; i){fscanf(pf, %d, data);ph.data[i] data;AdJustUp(ph.data, i);}while (fscanf(pf, %d, data) ! EOF){if(dataph.data[0])Swap(data, ph.data[0]);AdJustDown(ph.data, 10, 0);}for (i 0; i 10; i){printf(%d , ph.data[i]);}fclose(pf);pf NULL;return 0;
}
运行结果如下 这就是我们经典的Top-k问题
4.总结 今天的内容到这里就结束了希望大家可以好好的理解今天的内容欢迎大家来三连。
