堆的向下调整算法和TOPK问题

#pragma once

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HeapNodeDataType;
typedef struct Heap
{
HeapNodeDataType* _a;
int _size;
int _capacity;
}Heap;
//堆向上调整
void AdjustUp(HeapNodeDataType* array, int n);
//堆向下调整
void AdjustDown(HeapNodeDataType* array, int n, int size);
//堆的初始化
void HeapInit(Heap* php);
//堆的销毁
void HeapDestory(Heap* php);
//堆的插入一个结点
void HeapPush(Heap* php, HeapNodeDataType data);
//堆的删除一个结点
void HeapPop(Heap* php);
//堆的出堆顶数据
HeapNodeDataType HeapTop(Heap* php);
//返回堆内有效个数
int HeapSize(Heap* php);
//交换函数
void Swap(HeapNodeDataType* a, HeapNodeDataType* b);
//判断堆是否为空
bool HeapEmpty(Heap* php);

2.堆的功能实现：

2.1 堆的插入：

在尾部插入，向上调整，跟父节点比较，若满足条件就交换它们

void HeapPush(Heap* php, HeapNodeDataType data)
{
assert(php);
if (php->_capacity == php->_size)
{
int newCapacity = php->_capacity == 0 ? 4 : php->_capacity * 2;
HeapNodeDataType* newArray = (HeapNodeDataType*)realloc(php->_a, sizeof(HeapNodeDataType) * newCapacity);
php->_a = newArray;
php->_capacity = newCapacity;
}
php->_a[php->_size] = data;
int child = php->_size;
php->_size++;
AdjustUp(php->_a, child);
}

2.2 堆的删除：

将堆顶元素跟堆尾元素交换，然后从堆顶开始向下调整

void HeapPop(Heap* php)
{
assert(php);
assert(php->_a);
Swap(&php->_a[0], &php->_a[php->_size - 1]);
php->_size--;
AdjustDown(php->_a, 0, php->_size);
}

2.3 堆排序：

利用向下调整算法建堆，然后将堆顶数据放到堆尾，堆内有效元素-1，再向下调整

void HeapSort(int* a, int n)
{
int parent = (n - 1 - 1) / 2;
while (parent >= 0)
{
AdjustDown(a, parent, n);
parent--;
}
for(int i = n - 1; i > 0; i--)
{
Swap(&a[0], &a[i]);
AdjustDown(a, 0, i);
}
}

2.4 向下调整建堆：

从最后一个父节点（(end-1 )/2）开始向下调整建堆，到根结点向下调整建堆结束

void AdjustDown(HeapNodeDataType* array, int n, int size)
{
assert(array);
int parent = n;
int child = n * 2 + 1;
if (child + 1 < size && array[child] > array[child + 1])
{
child = n * 2 + 2;
}

while (child < size)
{
if (array[child] < array[parent])
{
Swap(&array[child], &array[parent]);
parent = child;
child = parent * 2 + 1;
if (child + 1 < size && array[child] > array[child + 1])
{
child = parent * 2 + 2;
}
}
else
{
break;
}
}
}

2.5 TOPK问题：

首先取前K个元素向下调整建堆，然后遍历剩下的元素，若满足条件则进堆

如果是取前k个最大的数，那么就建小堆

如果是取前k个最小的数，那么就建大堆

void CreateNDate()//创建一个有100000个数的文件
{
// 
int n = 100000;
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() % 100000;
fprintf(fin, "%d\n", x);
}

fclose(fin);
}

void PrintTopK(int k)
{
int* arr = (int*)malloc(sizeof(int) * k);
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < k; i++)
{
fscanf(fout,"%d", &arr[i]);
}
for (int i = (k - 1 - 1)/ 2; i >= 0; i--)
{
AdjustDown(arr, i, k);
}
int x = 0;
while (fscanf(fout, "%d", &x) > 0)
{
if (x > arr[0])
{
arr[0] = x;
AdjustDown(arr, 0, k);
}
}
printf("ǰ%d", k);
for (int i = 0; i < k; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}

2.6 向上调整算法：

参数：需要数组的首元素地址，数组的有效元素个数

首先创建parent保存父亲结点

若父亲节点小于0则循环结束

判断父节点和子节点，若满足条件则交换，将父亲的值给孩子，继续求孩子结点的父节点

如果判断不需要交换则break

void AdjustUp(HeapNodeDataType* array, int n)
{
assert(array);
int child = n;
while (child > 0)
{
int parent = (child - 1) / 2;
if (array[child] > array[parent])
{
Swap(&array[child], &array[parent]);
child = parent;
}
else
{
break;
}
}
}

2.7 向下调整算法：

参数：数组的首元素地址，从什么下表开始向下调整，数组的有效元素个数

已知父亲结点，求左孩子和右孩子结点，判断左右孩子的大小，假设法找到符合条件的哪一个

当孩子结点小于或等于堆内有效元素-1的时候进入循环，孩子结点大于size-1的时候循环结束

比较父子结点，判断是否需要交换

需要交换则将孩子给给父亲，运用假设法继续求孩子的结点中符合条件的那个

不需要交换则break

注意：在比较左右孩子谁满足条件时，需要判断右孩子是否存在，也即右孩子的下表需要小于size

void AdjustDown(HeapNodeDataType* array, int n, int size)
{
assert(array);
int parent = n;
int child = n * 2 + 1;
if (child + 1 < size && array[child] > array[child + 1])
{
child = n * 2 + 2;
}

while (child < size)
{
if (array[child] < array[parent])
{
Swap(&array[child], &array[parent]);
parent = child;
child = parent * 2 + 1;
if (child + 1 < size && array[child] > array[child + 1])
{
child = parent * 2 + 2;
}
}
else
{
break;
}
}
}

2.8 堆的初始化/返回堆顶元素/返回堆内有效元素个数/堆的判空/堆的销毁

void HeapInit(Heap* php)
{
assert(php);
php->_a = NULL;
php->_capacity = php->_size = 0;
}
void HeapDestory(Heap* php)
{
assert(php);
assert(php->_a);
free(php->_a);
php->_capacity = php->_size = 0;
}
HeapNodeDataType HeapTop(Heap* php)
{
assert(php);
assert(php->_a);
return php->_a[0];
}
int HeapSize(Heap* php)
{
assert(php);
return php->_size;
}
void Swap(HeapNodeDataType* a, HeapNodeDataType* b)
{
HeapNodeDataType tmp = *b;
*b = *a;
*a = tmp;
}
bool HeapEmpty(Heap* php)
{
return php->_size == 0;
assert(php);
}

原文地址：https://blog.csdn.net/qq_64105689/article/details/142383839

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：IP Source Guard技术原理与应用
下一篇：在Windows环境下设置SSH克隆GitHub仓库

rabbitmq 短信验证码
新建一个springboot项目,引入web，redis，rabbitmq。
阅读更多2024-09-21
tomcat中间件漏洞CVE-2017-12615，后台弱口令部署war包，CVE-2020-1938
2. ⽂件上传成功后，默认会在⽹站根⽬录下⽣成和war包名称⼀致得⽬录，然后⽬录中得⽊⻢就是压缩前的⽂件名。漏洞复现 http://172.16.1.22:8080/manager/html。制作W
阅读更多2024-09-21
力扣 438找到字符串中所有字母异位词
通过滑动窗口进行遍历，通过"hash"将字符串子串映射到异位词表示空间每一个表示代表了一个异位词空间(一个字符串的所有元素的全排列广义上讲，以上方法都属于一种hash。
阅读更多2024-09-21
数据结构 - 树与二叉树
/数据域//左结点与右结点的指针。
阅读更多2024-09-21
【STL】map和set相关知识详细梳理
1. set是按照一定次序存储元素的容器。2. 在set中，元素的value就是key，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除
阅读更多2024-09-21
Day4:杨辉三角
题目：给定一个非负整数numRows,生成杨辉三角的前numRows行。在杨辉三角中，每个数就是左上方和右上方数的和。
阅读更多2024-09-21
Android Retrofit源码分析（一）：Retrofit是什么？和OkHttp的区别是什么？为什么需要他？
为什么会出现Retrofit？它的作用是什么？
阅读更多2024-09-21
微服务远程调用（nacos及OpenFeign简单使用）
问题：在微服务中，每个项目是隔离开的，当有一个项目请求其他项目中的数据时，必须发起网络请求，本文即对此问题展开讨论。
阅读更多2024-09-21
数字签名和CA数字证书的核心原理
看了蛋老师的视频就很容易理解了，首先对服务器的公钥和信息进行哈希运算得到一个短字符串，然后用CA机构中的私钥对这一短字符串进行加密就得到了一个数字签名，然后就这个数字签名放到数字证书中，同时服务器的公
阅读更多2024-09-21
git 操作远程别名
【代码】git 操作远程别名。
阅读更多2024-09-21