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

相关文章

Vue3绑定props默认值问题

《Vue3绑定props默认值问题》使用Vue3的defineProps配合TypeScript的interface定义props类型,并通过withDefaults设置默认值,使组件能安全访问传入的... 目录前言步骤步骤1:使用 defineProps 定义 Props步骤2:设置默认值总结前言使用T

SpringBoot日志级别与日志分组详解

《SpringBoot日志级别与日志分组详解》文章介绍了日志级别(ALL至OFF)及其作用,说明SpringBoot默认日志级别为INFO,可通过application.properties调整全局或... 目录日志级别1、级别内容2、调整日志级别调整默认日志级别调整指定类的日志级别项目开发过程中,利用日志

Java中的抽象类与abstract 关键字使用详解

《Java中的抽象类与abstract关键字使用详解》:本文主要介绍Java中的抽象类与abstract关键字使用详解,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、抽象类的概念二、使用 abstract2.1 修饰类 => 抽象类2.2 修饰方法 => 抽象方法,没有

MySQL8 密码强度评估与配置详解

《MySQL8密码强度评估与配置详解》MySQL8默认启用密码强度插件,实施MEDIUM策略(长度8、含数字/字母/特殊字符),支持动态调整与配置文件设置,推荐使用STRONG策略并定期更新密码以提... 目录一、mysql 8 密码强度评估机制1.核心插件:validate_password2.密码策略级

从入门到精通详解Python虚拟环境完全指南

《从入门到精通详解Python虚拟环境完全指南》Python虚拟环境是一个独立的Python运行环境,它允许你为不同的项目创建隔离的Python环境,下面小编就来和大家详细介绍一下吧... 目录什么是python虚拟环境一、使用venv创建和管理虚拟环境1.1 创建虚拟环境1.2 激活虚拟环境1.3 验证虚

详解python pycharm与cmd中制表符不一样

《详解pythonpycharm与cmd中制表符不一样》本文主要介绍了pythonpycharm与cmd中制表符不一样,这个问题通常是因为PyCharm和命令行(CMD)使用的制表符(tab)的宽... 这个问题通常是因为PyCharm和命令行(CMD)使用的制表符(tab)的宽度不同导致的。在PyChar

sky-take-out项目中Redis的使用示例详解

《sky-take-out项目中Redis的使用示例详解》SpringCache是Spring的缓存抽象层,通过注解简化缓存管理,支持Redis等提供者,适用于方法结果缓存、更新和删除操作,但无法实现... 目录Spring Cache主要特性核心注解1.@Cacheable2.@CachePut3.@Ca

SpringBoot请求参数传递与接收示例详解

《SpringBoot请求参数传递与接收示例详解》本文给大家介绍SpringBoot请求参数传递与接收示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录I. 基础参数传递i.查询参数(Query Parameters)ii.路径参数(Path Va

RabbitMQ 延时队列插件安装与使用示例详解(基于 Delayed Message Plugin)

《RabbitMQ延时队列插件安装与使用示例详解(基于DelayedMessagePlugin)》本文详解RabbitMQ通过安装rabbitmq_delayed_message_exchan... 目录 一、什么是 RabbitMQ 延时队列? 二、安装前准备✅ RabbitMQ 环境要求 三、安装延时队

从基础到高级详解Python数值格式化输出的完全指南

《从基础到高级详解Python数值格式化输出的完全指南》在数据分析、金融计算和科学报告领域,数值格式化是提升可读性和专业性的关键技术,本文将深入解析Python中数值格式化输出的相关方法,感兴趣的小伙... 目录引言:数值格式化的核心价值一、基础格式化方法1.1 三种核心格式化方式对比1.2 基础格式化示例