王者荣耀战区活跃度排名怎么实现的？这篇文章给你答案！

news/2024/11/25 13:18:45/

🍉博客主页:阿博历练记
📖文章专栏:数据结构与算法
🚍代码仓库:阿博编程日记
🍥欢迎关注:欢迎友友们点赞收藏+关注哦🌹

在这里插入图片描述

文章目录

    • 🌈前言
    • 🍪堆的实现
      • 🔍1.堆的结构框架
      • 🔍2.堆的初始化
      • 🔍3.堆的插入数据
      • 🪄向上调整算法
      • ⭐求父亲结点
      • ⭐注意break
      • ⭐while循环的条件
      • 🔍4.堆的删除数据（默认规定删除堆顶的数据）
      • 🪄向下调整算法
      • 💯假设法
      • ⭐没有右孩子
      • ⭐while循环的结束条件
      • 🍁向上调整和向下调整算法前提
      • 🔍5.堆的判空
      • 🔍6.取堆顶数据
      • ⭐注意判空
      • 🔍7.返回堆中数据的个数
      • ⭐堆插入数据和删除数据的时间复杂度
      • 🔍8.堆的销毁
      • 🎎堆排序
      • ⭐升序和降序是建小堆还是大堆
      • 🎮向下调整建堆的时间复杂度
      • 🎮向上调整建堆的时间复杂度
      • 🎮堆排序的时间复杂度
      • 🎎Topk问题
      • ⭐生成数据放在文件中
      • ⭐打印前k个最大的数据
      • ⭐第二次fscanf读写的位置
      • ⭐验证程序是否正确
      • 🍗heap.h代码
      • 🍗heap.c代码
      • 🍗test.c代码

🌈前言

堆的概念及结构：
在这里插入图片描述
堆的性质：
1.堆中某个节点的值总是不大于或不小于其父节点的值；
大堆：树中任何一个父亲都大于等于孩子。
小堆：树中任何一个父亲都小于等于孩子。
2.堆总是一棵完全二叉树。
在这里插入图片描述
🔫堆并不代表有序，因为堆只规定了父亲和孩子结点的关系，对于左右孩子结点的大小关系我们是不确定的.这里阿博给友友们介绍几个堆的应用：1.堆排序(时间复杂度是N*logN) 2.topk问题3.优先级队列

🍪堆的实现

友友们，因为堆的物理结构就是一个数组，所以这里我们的底层结构是用数组实现的.

🔍1.堆的结构框架

typedef  int  HPDataType;
typedef  struct  Heap
{HPDataType* a;int  size;int  capacity;
}HP;

🔍2.堆的初始化

void  HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = 0;php->size = 0;
}

🔍3.堆的插入数据

void  HeapPush(HP* php,HPDataType x)
{assert(php);if (php->size == php->capacity){int  newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

在这里插入图片描述

🪄向上调整算法

void  AdjustUp(HPDataType*a, int child)       //向上调整算法
{int parent = (child - 1) / 2;while (child>0)              //这里while循环的条件不能写成parent>=0，因为我们的parent是根本不可能小于0的，就算child来到了根结点，parent还是根节点，它还是可以进循环，逻辑不正确，这里我们的逻辑就是当孩子{                                 //来到根节点时，它就没有父结点了，所以此时我们终止循环，所以这里的条件是当child来到根节点时，就不要进入循环了       if (a[child] < a[parent]){HPDataType  tmp = a[child];a[child] = a[parent];                       //小堆a[parent] = tmp;child = parent;parent = (child - 1) / 2;}else{break;}}
}

⭐求父亲结点

在这里插入图片描述

⭐注意break

在这里插入图片描述

⭐while循环的条件

友友们注意，这里while循环的条件不能写成parent>=0，因为父亲结点不会小于0，这里我们的逻辑就是当孩子结点来到根结点时就不要再进行比较了，这里如果用parent的话，当孩子结点来到根结点时，parent=(child-1)/2还是等于0，还是可以进循环，这里虽然结果不受影响，但是逻辑是不正确的，所以这里我们用child进行判断，当孩子结点来到根节点时，也就是child==0的时候，就不要再进入循环了.

🔍4.堆的删除数据（默认规定删除堆顶的数据）

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) ;
}

1.挪动删除数据，重新建堆
在这里插入图片描述
2.首尾数据交换，再删除，再调堆
在这里插入图片描述

🪄向下调整算法

void  AdjustDown(int* a, int n,int parent)
{int child = parent * 2 + 1; while (child<n){if (child+1<n&&a[child] > a[child + 1]){child++;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

💯假设法

友友们注意，这里用假设法，首先定义一个child为左孩子，假设左孩子是最小的，如果右孩子比左孩子小，那么child++，虽然我们不知道child是左孩子还是右孩子，但是它一定是左右孩子中最小的结点，如果没有采用这一种方法的话，我们就需要定义一个左孩子结点和右孩子结点，然后先让它们两个进行比较，最小的再和parent比较，这样就会出现代码大量的冗余.

⭐没有右孩子

在这里插入图片描述
这里友友们需要注意一下，因为堆是一个完全二叉树，它最后一层结点不是满的，但一定是连续的，所以我们需要注意一下右孩子结点不存在的情况，在比较左右孩子结点的时候，需要保证右孩子结点存在，否则就可能会出现越界访问.

⭐while循环的结束条件

友友们，这里我们的逻辑是每次向下调整的时候都需要对父亲结点和孩子结点进行比较，当孩子结点不存在的时候，我们就不需要进行比较了，也就是孩子结点的下标大于等于n，又因为堆是一颗完全二叉树，当左孩子结点不存在时，右孩子结点一定不存在，所以这里我们只需要判断左孩子结点是否存在就可以了.

🍁向上调整和向下调整算法前提

1.向上调整算法：在向上调整时，必须要保证调整前是堆
2.向下调整算法：必须要保证左右孩子是堆

🔍5.堆的判空

bool  HeapEmpty(HP* php)
{assert(php);return  php->size == 0;
}

🔍6.取堆顶数据

HPDataType  HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return   php->a[0];
}

⭐注意判空

友友们如果我们这里没有判空的话，就会出现下面三种情况：
🎲1.如果堆内有元素，那就是正常的获取堆顶元素.
🎲2.插入一个元素，再删除一个元素，此时堆已经为空了，但是如果我们没有判空的话，我们拿到的就是a[0]的数据，这就是不正确的.
🎲3.我们初始化的时候malloc了一块空间，此时堆顶的数据就是随机值.

🔍7.返回堆中数据的个数

int   HeapSize(HP* php)
{assert(php);return   php->size;
}

⭐堆插入数据和删除数据的时间复杂度

在这里插入图片描述

🔍8.堆的销毁

void  HeapDetroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

🎎堆排序

1.拷贝堆顶数据放到数组里面

void  HeapSort (int*a,int n)
{HP  hp;HeapInit(&hp);int  i = 0;for (int i = 0; i < n; i++){HeapPush(&hp, a[i]);}while (!HeapEmpty(&hp)){a[i++] = HeapTop(&hp);          HeapPop(&hp);}HeapDestroy(&hp);
}

友友们，虽然这种方法可行，但是有两个弊端：1.需要先有一个堆，比较麻烦.2.空间复杂度+拷贝数据

2.对数组向上调整建堆

void  HeapSort(int* a, int n)
{向上调整建堆for (int i = 1; i < n; i++){AdjustUp(a, i);}int  end = 0;for (end = n; end > 1;){swap(&a[0], &a[end-1]);end--;AdjustDown(a, end, 0);}
}

在这里插入图片描述

⭐升序和降序是建小堆还是大堆

在这里插入图片描述

3.对数组向下调整建堆

void  HeapSort(int* a, int n)
{
//	//向下调整建堆for (int i = (n-1-1)/2; i>=0; i--){AdjustDown(a, n, i);}int  end = 0;for (end = n; end > 1;){swap(&a[0], &a[end - 1]);end--;AdjustDown(a, end, 0);}
}

在这里插入图片描述

🎮向下调整建堆的时间复杂度

在这里插入图片描述

🎮向上调整建堆的时间复杂度

在这里插入图片描述

🎮堆排序的时间复杂度

在这里插入图片描述

🎎Topk问题

⭐生成数据放在文件中

void  CreateNDate()
{srand((unsigned int)time(0));int  n = 1000;const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen  fail");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)
{const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen  fail");return;}int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc  fail");return;}for (int i = 0; i < k; i++){fscanf(fout,"%d",&kminheap[i]);}for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}int  value = 0;while (!feof(fout)){fscanf(fout,"%d",&value);                //注意这里文件指针已经不是从头开始读了，因为前面文件指针已经读取k个数据了if (value > kminheap[0]){swap(&value, &kminheap[0]);AdjustDown(kminheap, k, 0);}}for (int i = 0; i < 5; i++){printf("%d ", kminheap[i]);}
}

在这里插入图片描述

⭐第二次fscanf读写的位置

友友们注意，第一次fscanf从文件中读取了前k个数据建小堆，文件指针来到了第k+1个位置，所以当我们建完小堆之后再次fscanf，它就会从第k+1个位置开始读数据.

⭐验证程序是否正确

友友们，这里我们无法确定我们打印的就是N个数据中最大的前K个，但是我们可以手动改变，因为我们生成的数都在1000000以内，所以我们可以写几个大于1000000的数据，如果它能打印出来，就证明我们这个程序是正确的.

在这里插入图片描述
在这里插入图片描述

🍗heap.h代码

#pragma once
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<stdio.h>
typedef  int  HPDataType;
typedef  struct  Heap
{HPDataType* a;int  size;int  capacity;
}HP;
void  HeapInit(HP* php);
void  HeapDestroy(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  AdjustUp(int* a, int child);
void  AdjustDown(int* a, int n, int parent);
void  swap(HPDataType* p1, HPDataType* p2);

🍗heap.c代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
void  HeapInit(HP* php)
{assert(php);php->a = NULL;php->capacity = 0;php->size = 0;
}
void  HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}
void  AdjustUp(int*a, int child)       //向上调整算法
{int parent = (child - 1) / 2;while (child>0)              //这里while循环的条件不能写成parent>=0，因为我们的parent是根本不可能小于0的，就算child来到了根结点，parent还是根节点，它还是可以进循环，逻辑不正确，这里我们的逻辑就是当孩子{                                 //来到根节点时，它就没有父结点了，所以此时我们终止循环，所以这里的条件是当child来到根节点时，就不要进入循环了       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){int  newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
void  swap(HPDataType* p1,HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void  AdjustDown(int* a, int n,int parent)
{int child = parent * 2 + 1; while (child<n){if (child+1<n&&a[child] > a[child + 1]){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);assert(!HeapEmpty(php));return   php->a[0];
}
bool  HeapEmpty(HP* php)
{assert(php);return  php->size == 0;
}
int   HeapSize(HP* php)
{assert(php);return   php->size;
}

🍗test.c代码

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
#include<time.h>
//int  main()
//{
//	HP  hp;
//	HeapInit(&hp);
//	int  arr[] = { 65,100,70,32,50,60 };
//	for (int i = 0; i < 6; i++)
//	{
//		HeapPush(&hp, arr[i]);
//	}
//	while (!HeapEmpty(&hp))
//	{
//		printf("%d\n", HeapTop(&hp));      //有序打印，不是排序
//		HeapPop(&hp);
//	}
//	return  0;
//}
//void  HeapSort (int*a,int n)
//{
//	HP  hp;
//	HeapInit(&hp);
//	int  i = 0;
//	for (int i = 0; i < n; i++)
//	{
//		HeapPush(&hp, a[i]);
//	}
//	while (!HeapEmpty(&hp))
//	{
//		a[i++] = HeapTop(&hp);           //弊端：1.先有一个堆，太麻烦 2.空间复杂度+拷贝数据
//		HeapPop(&hp);
//	}
//	HeapDestroy(&hp);
//}
void  HeapSort(int* a, int n)
{向上调整建堆//for (int i = 1; i < n; i++)//{//	AdjustUp(a, i);//}//int  end = n;//while(end>1)//{//	swap(&a[0], &a[end-1]);//	end--;//	AdjustDown(a, end, 0);//}//向下调整建堆for (int i = (n-1-1)/2; i>=0; i--){AdjustDown(a, n, i);}int  end = n;while(end>1){swap(&a[0], &a[end - 1]);end--;AdjustDown(a, end, 0);}
}
void  CreateNDate()
{srand((unsigned int)time(0));int  n = 1000;const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen  fail");return;}for (size_t i = 0; i < n; i++){int x = rand()%1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}
void  PrintTopk(int k)
{const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen  fail");return;}int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc  fail");return;}for (int i = 0; i < k; i++){fscanf(fout,"%d",&kminheap[i]);}for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(kminheap, k, i);}int  value = 0;while (!feof(fout)){fscanf(fout,"%d",&value);                //注意这里文件指针已经不是从头开始读了，因为前面文件指针已经读取k个数据了if (value > kminheap[0]){swap(&value, &kminheap[0]);AdjustDown(kminheap, k, 0);}}for (int i = 0; i < 5; i++){printf("%d ", kminheap[i]);}printf("\n");
}
int  main()
{/*top问题10000个数中，找出最大的前十个建立大堆，pop9次*/int  a[] = { 7,8,3,5,1,9,5,4 };HeapSort(a, sizeof(a) / sizeof(a[0]));/*文件中找Topk问题*///CreateNDate();PrintTopk(5);return  0;
}

http://www.ppmy.cn/news/231362.html

相关文章

创业初始，王兴每周工作超过100小时，互联网巨头各有各的辛酸

创业初始，王兴每周工作超过100小时，互联网巨头各有各的辛酸

来源&#xff1a; 猎云网&#xff08;ilieyun&#xff09; 作者&#xff1a;颜西龙 2011 年 8 月 16 日&#xff0c;北京 798 艺术中心。 台上&#xff0c;雷军每公布一项技术参数&#xff0c;台下就传来一阵几乎要掀翻屋顶的声浪。 一位记者问&#xff1a;「这都是哪请来的托&…
阅读更多...
移动互联网十年，谁主沉浮？

移动互联网十年，谁主沉浮？

2011年8月16日&#xff0c;北京798艺术中心。 台上&#xff0c;雷军每公布一项技术参数&#xff0c;台下就传来一阵几乎要掀翻屋顶的声浪。 一位记者问&#xff1a;“这都是哪请来的托&#xff0c;太敬业了&#xff01;”工作人员只得实话实说&#xff1a;“都是自己来的&#…
阅读更多...
面试：第十二章：所有总结

面试：第十二章：所有总结

Java基础 java基本类型哪些&#xff0c;所占字节 byte &#xff1a;1个字节 short &#xff1a;2个字节 char &#xff1a;2个字节 int &#xff1a;4个字节 long &#xff1a;8个字节 float &#xff1a;4个字节 double &#xff1a;8个字节 java集合以及底层原理 Ja…
阅读更多...
《定位》阅读笔记

《定位》阅读笔记

什么是定位&#xff1f; 定义 定位是你对预期客户做的事情基本方法是改变人们头脑里早已存在的东西&#xff0c;把那些早已存在的联系重新连接到一起 产生原因 过分传播的社会&#xff1a;美国每年的广告消费人均200美金。在这个传播过度的丛林里&#xff0c;获得大成功的唯一希…
阅读更多...
综合金融服务方案模板

综合金融服务方案模板

XX省咨询投资集团有限公司 综 合 金 融 服 务 方 案 XX银行股份有限公司 二零一九年四月 前 言 XX省咨询投资集团有限公司&#xff1a; 首先&#xff0c;衷心地感谢贵司给我行提供此次宝贵的合作机会&#xff01;我行高度重视此次合作&#xff0c;选拔骨干力量组成了…
阅读更多...
快手CEO宿华14年

快手CEO宿华14年

本文为PMCAFF作者 盐汽水&善宝橘 于社区发布 中国近代史上&#xff0c;湖南所产生的改革者、革命家之多&#xff0c;居中国诸省之冠。曾国藩&#xff0c;郭嵩焘&#xff0c;谭嗣同&#xff0c;陈天华&#xff0c;毛泽东等改变中国历史走向的变革者均是湖南人。 正是这些变革…
阅读更多...
java面试突击

java面试突击

时间 版本 说明 2019-2-27 v 1.0 初版发布 2019-3-2 v 2.0 对于第一版进行了大幅度更新&#xff0c;除了修改了一些小错误之外&#xff0c;还增加了一些内容。 2019-4-18 v3.0 修复错误&#xff0c;完善内容&#xff0c;增加了少部分内容。 必看 本文档由 SnailClimb 整理&…
阅读更多...
Edsger Wybe Dijkstra

Edsger Wybe Dijkstra

埃德斯加狄克斯特拉&#xff08;Edsger Wybe Dijkstra&#xff09;&#xff08;May 11, 1930 – August 6, 2002;&#xff09;是1950年代ALGOL语言的一个主要贡献者。ALGOL高级编程语言已经成为结构清晰&#xff0c;数学基础严谨的一个典范。E. W. Dijkstra是现代编程语言的主要…
阅读更多...
最新文章

Copyright @ 2022~2023