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

相关文章

线上Java OOM问题定位与解决方案超详细解析

《线上JavaOOM问题定位与解决方案超详细解析》OOM是JVM抛出的错误,表示内存分配失败,:本文主要介绍线上JavaOOM问题定位与解决方案的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一、OOM问题核心认知1.1 OOM定义与技术定位1.2 OOM常见类型及技术特征二、OOM问题定位工具

PHP轻松处理千万行数据的方法详解

《PHP轻松处理千万行数据的方法详解》说到处理大数据集,PHP通常不是第一个想到的语言,但如果你曾经需要处理数百万行数据而不让服务器崩溃或内存耗尽,你就会知道PHP用对了工具有多强大,下面小编就... 目录问题的本质php 中的数据流处理:为什么必不可少生成器:内存高效的迭代方式流量控制:避免系统过载一次性

C++右移运算符的一个小坑及解决

《C++右移运算符的一个小坑及解决》文章指出右移运算符处理负数时左侧补1导致死循环,与除法行为不同,强调需注意补码机制以正确统计二进制1的个数... 目录我遇到了这么一个www.chinasem.cn函数由此可以看到也很好理解总结我遇到了这么一个函数template<typename T>unsigned

MySQL的JDBC编程详解

《MySQL的JDBC编程详解》:本文主要介绍MySQL的JDBC编程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、前置知识1. 引入依赖2. 认识 url二、JDBC 操作流程1. JDBC 的写操作2. JDBC 的读操作总结前言本文介绍了mysq

Redis 的 SUBSCRIBE命令详解

《Redis的SUBSCRIBE命令详解》Redis的SUBSCRIBE命令用于订阅一个或多个频道,以便接收发送到这些频道的消息,本文给大家介绍Redis的SUBSCRIBE命令,感兴趣的朋友跟随... 目录基本语法工作原理示例消息格式相关命令python 示例Redis 的 SUBSCRIBE 命令用于订

使用Python批量将.ncm格式的音频文件转换为.mp3格式的实战详解

《使用Python批量将.ncm格式的音频文件转换为.mp3格式的实战详解》本文详细介绍了如何使用Python通过ncmdump工具批量将.ncm音频转换为.mp3的步骤,包括安装、配置ffmpeg环... 目录1. 前言2. 安装 ncmdump3. 实现 .ncm 转 .mp34. 执行过程5. 执行结

Python中 try / except / else / finally 异常处理方法详解

《Python中try/except/else/finally异常处理方法详解》:本文主要介绍Python中try/except/else/finally异常处理方法的相关资料,涵... 目录1. 基本结构2. 各部分的作用tryexceptelsefinally3. 执行流程总结4. 常见用法(1)多个e

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法

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、调整日志级别调整默认日志级别调整指定类的日志级别项目开发过程中,利用日志