6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

2024-09-09 16:28

本文主要是介绍6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客

本章重点

1.使用堆来完成堆排序

2.使用堆解决TopK问题

目录

一.堆排序

1.1 思路

1.2 代码

1.3 简单测试

二.TopK问题

2.1 思路(求最小):

2.2 C语言代码(手写堆)

2.3 C++代码(使用优先级队列 priority_queue)


一.堆排序

1.1 思路

        由于堆的特殊性质,可以使用堆来堆数组进行排序,而且效率较高。

这里以排降序为例。

1.根据数组建堆

2.排序

        a.将堆顶数据和最后一个数据交换,n--

        b.0~n -1位置还满足向下调整算法。再次调整为堆

        c.继续交换

如下图

排升序:建立大根堆

排降序:建立小根堆

1.2 代码

//降序为例
void HeapSort(int* arr, int n)
{//1.将数组建堆,使用向下调整算法建立小根堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){Adjustdown(arr, n, i);}//2.排序//a.将堆顶数据和最后一个数据交换,再让n--,//b.此时0~n-1还是可以使用调整算法调整为堆//c.继续交换int end = n - 1;while (end >= 0){swap(arr[0], arr[end]);Adjustdown(arr, end, 0);end--;}
}

1.3 简单测试

 测试主函数代码如下

int main()
{DataType arr[] = { 1,5,9,7,5,3,4,6,8,2,4,4,15,19,59,75,73,53,46,82 };cout << "排序前:" << endl;for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){cout << arr[i] << " ";}cout << endl << "排序后:" << endl;HeapSort(arr, sizeof(arr) / sizeof(arr[0]));for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++){cout << arr[i] << " ";}return 0;
}

测试结果

二.TopK问题

TopK问题是,如何从n个数据中找出前k个最大,或者最小的数据。

Leetcode原题:面试题 17.14. 最小K个数 - 力扣(LeetCode)

2.1 思路(求最小):

1. 我们建立一个大小为 k 的堆

2. 求最小,建立大根堆。求最大,建立小根堆。

3. 遍历数组,遇到比堆顶数据小的数据 i 时,将数据 i 替换堆顶。然后对堆使用向下调整

2.2 C语言代码(手写堆)

此代码可以直接在题目中运行通过

//向下调整算法,求最小,建立大根堆
void Adjustdown(int*arr,int n,int root)
{int parent=root;int child=parent*2+1;while(child<n){if(child+1<n && arr[child]<arr[child+1] )child++;if(arr[child]>arr[parent]){int t=arr[child];arr[child]=arr[parent];arr[parent]=t;parent=child;child=parent*2+1;}else{break;}}
}int* smallestK(int* arr, int arrSize, int k, int* returnSize)
{*returnSize=k;if(*returnSize==NULL)return NULL;//定义k大小的数组,并拷贝前k个数据,并且调整为堆int *Rarr=(int*)malloc(sizeof(int)*k);for(int i=0;i<k;i++){Rarr[i]=arr[i];}for(int i=(k-1-1)/2;i>=0;i--){Adjustdown(Rarr,k,i);}//TopK法,遍历原数组,遇到比堆顶还要小,删堆顶,插入新元素//这里从k开始,是因为前面已经拷贝了k个数据for(int i=0;i<k;i++){printf("%d ",Rarr[i]);}printf("\n");for(int i=k;i<arrSize;i++){if(arr[i]<Rarr[0]){//1.替换数据Rarr[0]=arr[i];//2.重新调整Adjustdown(Rarr,k,0);}}return Rarr;
}

2.3 C++代码(使用优先级队列 priority_queue)

        优先级队列 priority_queue 就是堆,此代码可以直接通过力扣题的测试

//优先级队列
//1.默认的为大根堆
priority_queue<int, vector<int>> pq;//使用greator为小根堆
priority_queue<int, vector<int>, greater<int>>pq;

解题代码

class Solution {
public:vector<int> smallestK(vector<int>& arr, int k) {vector<int> retarr(k);if(k==0)return retarr;//使用优先级队列建立大根堆priority_queue<int,vector<int>> pq;//1.拷贝k个数据for(int i=0;i<k;i++){pq.push(arr[i]);}//2.遍历数组,替换比堆顶大的数据for(int i=k;i<arr.size();i++){if(arr[i]<pq.top()){pq.pop();pq.push(arr[i]);}}for(int i=0;i<k;i++){retarr[i]=pq.top();pq.pop();}return retarr;}
};

这篇关于6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1151677

相关文章

Spring Boot 整合 ShedLock 处理定时任务重复执行的问题小结

《SpringBoot整合ShedLock处理定时任务重复执行的问题小结》ShedLock是解决分布式系统中定时任务重复执行问题的Java库,通过在数据库中加锁,确保只有一个节点在指定时间执行... 目录前言什么是 ShedLock?ShedLock 的工作原理:定时任务重复执行China编程的问题使用 Shed

一文详解Java Condition的await和signal等待通知机制

《一文详解JavaCondition的await和signal等待通知机制》这篇文章主要为大家详细介绍了JavaCondition的await和signal等待通知机制的相关知识,文中的示例代码讲... 目录1. Condition的核心方法2. 使用场景与优势3. 使用流程与规范基本模板生产者-消费者示例

使用C/C++调用libcurl调试消息的方式

《使用C/C++调用libcurl调试消息的方式》在使用C/C++调用libcurl进行HTTP请求时,有时我们需要查看请求的/应答消息的内容(包括请求头和请求体)以方便调试,libcurl提供了多种... 目录1. libcurl 调试工具简介2. 输出请求消息使用 CURLOPT_VERBOSE使用 C

开启mysql的binlog日志步骤详解

《开启mysql的binlog日志步骤详解》:本文主要介绍MySQL5.7版本中二进制日志(bin_log)的配置和使用,文中通过图文及代码介绍的非常详细,需要的朋友可以参考下... 目录1.查看是否开启bin_log2.数据库会把日志放进logs目录中3.查看log日志总结 mysql版本5.71.查看

C++实现获取本机MAC地址与IP地址

《C++实现获取本机MAC地址与IP地址》这篇文章主要为大家详细介绍了C++实现获取本机MAC地址与IP地址的两种方式,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实际工作中,项目上常常需要获取本机的IP地址和MAC地址,在此使用两种方案获取1.MFC中获取IP和MAC地址获取

MYSQL事务死锁问题排查及解决方案

《MYSQL事务死锁问题排查及解决方案》:本文主要介绍Java服务报错日志的情况,并通过一系列排查和优化措施,最终发现并解决了服务假死的问题,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录问题现象推测 1 - 客户端无错误重试配置推测 2 - 客户端超时时间过短推测 3 - mysql 版本问

C/C++通过IP获取局域网网卡MAC地址

《C/C++通过IP获取局域网网卡MAC地址》这篇文章主要为大家详细介绍了C++如何通过Win32API函数SendARP从IP地址获取局域网内网卡的MAC地址,感兴趣的小伙伴可以跟随小编一起学习一下... C/C++通过IP获取局域网网卡MAC地址通过win32 SendARP获取MAC地址代码#i

deepseek本地部署使用步骤详解

《deepseek本地部署使用步骤详解》DeepSeek是一个开源的深度学习模型,支持自然语言处理和推荐系统,本地部署步骤包括克隆仓库、创建虚拟环境、安装依赖、配置模型和数据、启动服务、调试与优化以及... 目录环境要求部署步骤1. 克隆 DeepSeek 仓库2. 创建虚拟环境3. 安装依赖4. 配置模型

Git提交代码详细流程及问题总结

《Git提交代码详细流程及问题总结》:本文主要介绍Git的三大分区,分别是工作区、暂存区和版本库,并详细描述了提交、推送、拉取代码和合并分支的流程,文中通过代码介绍的非常详解,需要的朋友可以参考下... 目录1.git 三大分区2.Git提交、推送、拉取代码、合并分支详细流程3.问题总结4.git push

Sentinel 断路器在Spring Cloud使用详解

《Sentinel断路器在SpringCloud使用详解》Sentinel是阿里巴巴开源的一款微服务流量控制组件,主要以流量为切入点,从流量路由、流量控制、流量整形、熔断降级、系统自适应过载保护、... 目录Sentinel 介绍同类对比Hystrix:Sentinel:微服务雪崩问题问题原因问题解决方案请