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

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

在这里插入图片描述

文章目录

- 🌈前言
- 🍪堆的实现
- - 🔍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;
}