深圳博纳网站建设,公司简介模板素材,wordpress4.9.3漏洞,管理咨询公司口号目录 一堆的向上调整算法二堆的向下调整算法三堆的应用:堆排序四TOPK问题 一堆的向上调整算法 我们在堆中插入一个数据一般实在堆的最后插入然后可以一步一步与上层结点#xff08;父结点进行比较#xff09;#xff0c;继而进行交换#xff0c;完成二叉树的结构#xff0… 目录 一堆的向上调整算法二堆的向下调整算法三堆的应用:堆排序四TOPK问题 一堆的向上调整算法 我们在堆中插入一个数据一般实在堆的最后插入然后可以一步一步与上层结点父结点进行比较继而进行交换完成二叉树的结构 其中我们就有公式父节点的下标孩子结点的下标-1/2就等价于parentchild-1/2 我们可以写一个方法让插入的数据与父结点进行比较直到合适的位置为止。 那么停下来就有两种情况 1一直交换到头结点停下。2交换到合适的位置但没有到头结点中途停下。 第一种情况一直到头结点因为每次都要 childparent; parent (child - 1) / 2; 所以当child到0没有父结点了就循环结束。
void AdjustUp(HeapType* 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;}}}void Swap(HeapType* a, HeapType* b) {HeapType* tem *a;*a *b;*b tem;}第二种情况因为中点调整好了当if语句没交换时候就可以结束循环调整完成了 加上else { break; }
void AdjustUp(HeapType* 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;}}}
二堆的向下调整算法 当我们要去删除一个大堆或者小堆的头结点的时候我们可以直接把尾部结点的数据和头部的交换然后把访问下标的数字-1.然后进行向下调整这样就可以建立二叉树的结构了 但是 我们有一个问题我们都知道parent(child-1)/2且有唯一一个父节点。但是我们让头结点进行向下调整的时候要去交换哪个孩子结点呢是否要判断? 如图这是个小堆头结点进行向下调整的时候需要判断跟哪个孩子交换必须保证是次小的孩子要不然就会出现父节点比孩子结点大就不是小堆了。大堆也是同样道理 判断代码如下
if (child 1 n a[child] a[child 1]) {child child 1;其中n是有效数据个数需要保证有两个孩子才能判断 向下调整算法代码如下 void AdjustDown(HeapType* a, int parent, int n) {int child parent * 2 1;while (child n){if (child 1 n a[child] a[child 1]) {child child 1;}if (a[parent] a[child]) {Swap(a[parent], a[child]);parent child;child child * 2 1;}else{break;}}}三堆的应用:堆排序
那么我们可以通过堆的结构来进行排序因为二叉树不是严格意义上的顺序结构它只保证父节点比孩子结点大或小。 我们可以实现一个算法来把堆的二叉树结构调整为升序或者降序。 具体实现方法为循环把头结点和尾结点进行交换因为头结点是一个结构最大或者最小的这时候我们把尾部结点减少一个在进行向下调整然后再进行交换把次大或次小的数据放到最后一个尾部结点减少一个向下调整…如此循环直到到最后一个数据向下调整。这样就变成有序的了。 因为大堆的头结点是最大的一开始放到尾结点这样就是升序反之小堆调整则为降序。 HeapSort2(a1, 6);
int sz sizeof(a1) / sizeof(a1[0]);
for (int i 0; i sz; i) {printf(%d ,a1[i]);
}
void HeapSort2(HeapType* arr, int n) {//进行向下调整建堆for (int i (n - 1 - 1) / 2; i 0; i--) {AdjustDown(arr, i, n);}int end n - 1;for (int i end; i 0; i--) {//小堆进行调整为降序Swap(arr[0], arr[end]);AdjustDown(arr, 0, end);end--;}
}四TOPK问题
我们在N个数据中找前topk大或者小的数据这类问题一般思路就是一个个进行比较这样空间复杂度太大。 我们可以先建立一个大小为k的堆然后通过后N-k个数据依次和堆的头结点进行比较判断是否入堆如果入堆就向下调整到合适位置这样数据读完我们就可以销毁文件那么空吉安复杂度则只有建立的堆然后堆的数据即为topk. 我们可以进行文件输入输出流来实现创造 N个数据 中间利用time函数利用写的方式把数据写道date,txt文件中 大小为不大于等于1000000 void CreateNDate()
{// 造数据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() % 1000000;fprintf(fin, %d\n, x);}fclose(fin);
}然后读取数据建立k个大小的堆再把文件后面数据和堆顶比较如果比堆顶大就进堆然后向下调整。 void PrintTopK() {int k 0;printf(请输入);scanf(%d,k);const char* file data.txt;FILE* fout fopen(file, r);if (fout NULL) {perror(error);}HeapType* pp (HeapType*)malloc(k * sizeof(HeapType));for (int i 0; i k; i) {fscanf(fout, %d, pp[i]);}for (int i (k - 1 - 1) / 2; i 0; i--) {AdjustDown(pp, i, k);}int x0;while (fscanf(fout, %d, x) ! EOF) {if (x pp[0]) {pp[0] x;AdjustDown(pp, 0, k);}}for (int i 0; i k;i) {printf(%d , pp[i]);}fclose(fout);}我们为了验证对不对可以修改两个数超过1000000然后输出看对不对 最后输出结果
