当前位置: 首页 > news >正文

专题五:优先级队列

"你了解我,最干净的轮廓, 握住小小风车和放肆的梦~" 


        堆是一个不错的数据结构,而在计算机中,无法表示二叉分支结构,因此我们经常会看到使用线性表来作为堆的存储容器。在接触堆的时候,我们是把它拿来同其他排序算法来看待的,但其实我们经常使用的是快排或者归并亦或者性能更加优越的"选择快排"。堆的应用场景,实质上转移到了查找问题,例如TopK等。很多语言也提供了以堆为底层的数据结构,例如C++中的priority_queue,Java中的PriorityQueue……

如何实现一个堆排序?

        我们对任意一个堆的定义是一个完全二叉树,当一个父节点的值,大于左右子节点的值,则称为大堆,反之如果一个父节点的值,小于左右节点的值,则被称之为小堆。

        建堆的方法有两种,一种是"向上调整法",一种是"向下调整法"。前者的思想是着眼于整个数组,后者的思想着眼于分治,先将最小的子树进行一次堆排序,再不停向上迭代。因为"向下调整法"实现起来更为简单,并且效率更高,所以我们选择后者。

(1) 构建一个堆(大堆)

// 找到最后的父节点
for (int i = (n - 1 - 1 ) / 2;i >= 0;--i)
{adjustDown(nums, i);
}void adjustDown(vector<int>& nums,int parent)
{// 控制下标int n = nums.size();int child = parent * 2 + 1;while (child < n){// 把更大的换上去if (child+1 < n && nums[child] < nums[child + 1]) child++;// 比较if (nums[parent] < nums[child]) {swap(nums[parent], nums[child]);// 更新parent = child;child = parent * 2 + 1;}else {// 结束break;}}
}

(2) 堆排序

        要实现"升序排序,构建大堆,反之构建小堆"(因为本篇不是着眼于堆排序,不解释)。

void adjustDown(vector<int>& nums,int parent,int end)
{// 控制下标int child = parent * 2 + 1;while (child < end){// 把更大的换上去if (child+1 < end && nums[child] < nums[child + 1]) child++;// 比较if (nums[parent] < nums[child]) {swap(nums[parent], nums[child]);// 更新parent = child;child = parent * 2 + 1;}else {// 结束break;}}
}void HeapSort(vector<int>& nums)
{// 建堆int n = nums.size();// 找到最后的父节点for (int i = (n - 1 - 1 ) / 2;i >= 0;--i){adjustDown(nums, i,n);}// 排序int end = n - 1;while (end > 0){// 因为构建的是大堆,所有后面的数一定是小数swap(nums[end], nums[0]); // 同堆顶交换 让最大的数 在最后一个adjustDown(nums, 0,end);// 排序好一个数end--;}for (auto& n : nums)cout << n << " ";cout << endl;
}

——前言


1、最后一块石头的重量

(1) 题目解析        

(2) 算法原理        

C++: 

class Solution {
public:int lastStoneWeight(vector<int>& stones) {// 寻找大数,构建大堆priority_queue<int,vector<int>,less<int>> heap;// 入队列for(auto& n:stones) heap.push(n);// 模拟出队列while(heap.size() > 1){int x = heap.top();heap.pop();int y = heap.top();heap.pop();// 插入差值heap.push(x-y);}return heap.size() == 0 ? 0:heap.top();}
};

Java:

class Solution {public int lastStoneWeight(int[] stones) {PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);for(int n:stones) heap.offer(n);// 模拟while(heap.size() > 1){int a = heap.poll();int b= heap.poll();heap.offer(a-b);}return heap.isEmpty() ? 0 : heap.peek();}
}

2、数据流中的第K大元素

(1) 题目解析

        这也是一个经典的topK问题,对于要找第K大的数,我们需要构建是小堆,而不是大堆。反之,要查找第K小的数,我们需要构建的是大堆,而不是小堆。

(2) 算法原理

c++: 

class KthLargest {
public:// 构建小堆priority_queue<int,vector<int>,greater<int>> _heap;int _k; // 构建多大的kKthLargest(int k, vector<int>& nums) {_k = k;// 入队列for(auto& n:nums){_heap.push(n);if(_heap.size() > _k) _heap.pop(); // 剔除多余数}}int add(int val) {_heap.push(val);if(_heap.size() > _k) _heap.pop();return _heap.top();}
};

 java:

class KthLargest {PriorityQueue<Integer> heap;int _k;public KthLargest(int k, int[] nums) {_k = k;heap = new PriorityQueue<>(); // 默认是小堆for(int x:nums){heap.offer(x);if(heap.size() > _k) heap.poll();}}public int add(int val) {heap.offer(val);if(heap.size() > _k) heap.poll();return heap.peek();}
}

3、前K个高频单词

(1) 题目解        

(2) 算法原理   

class Solution {
public:typedef pair<int,string> PSI; // 频次与字符串 用于比较struct cmp{template<class T>bool operator()(T& t1,T& t2){return (t1.first > t2.first) || (t1.first == t2.first) && (t1.second < t2.second);}};vector<string> topKFrequent(vector<string>& words, int k) {unordered_map<string,int> hash; // 统计频次for(auto& str:words) hash[str]++;// 普通的比较函数: less\greater 不能满足我们的要求// 所以我们得更换比较函数: 这里我们采用的是 仿函数priority_queue<PSI,vector<PSI>,cmp> heap;for(auto& n:hash){heap.push({n.second,n.first});if(heap.size() > k) heap.pop();}// 倒序vector<string> ret(k);for(int i=k-1;i>=0;--i){ret[i] = heap.top().second;heap.pop();}return ret;}
};


4、数据流中的中位数

(1) 题目解析        

        前两者解法都是很好想的,前提就是保证数组有序,再来找中位数。但,我们这里选择的解法不是其中的任意一种。

(2) 算法原理        

class MedianFinder {
public:priority_queue<int,vector<int>,less<int>> _left;priority_queue<int,vector<int>,greater<int>> _right;MedianFinder() {}void addNum(int num) {if(_left.size() == _right.size()){if(_left.empty() || num <= _left.top()){// 直接进入_left.push(num);}else{// 替换_right.push(num);_left.push(_right.top());_right.pop();}}else{if(num <= _left.top()){_left.push(num);_right.push(_left.top());_left.pop();}else{_right.push(num);}}}double findMedian() {if(_left.size() == _right.size()) return (_left.top() + _right.top()) / 2.0;return _left.top(); // m=n+1}
};

本篇到此结束,感谢你的阅读。

祝你好运,向阳而生~

相关文章:

专题五:优先级队列

"你了解我&#xff0c;最干净的轮廓&#xff0c; 握住小小风车和放肆的梦~" 堆是一个不错的数据结构&#xff0c;而在计算机中&#xff0c;无法表示二叉分支结构&#xff0c;因此我们经常会看到使用线性表来作为堆的存储容器。在接触堆的时候&#xff0c;我们是把它…...

游戏设计模式专栏(一):工厂方法模式

引言 大家好&#xff0c;我是亿元程序员&#xff0c;一位有着8年游戏行业经验的主程。 本系列是《和8年游戏主程一起学习设计模式》&#xff0c;让糟糕的代码在潜移默化中升华&#xff0c;欢迎大家关注分享收藏订阅。 在游戏开发中&#xff0c;代码的组织和结构对于项目的可…...

element中使用el-steps 进度条效果demo(整理)

<template><div class"margin-top20"><!-- align-center 不要居中就去掉 --><!-- process-status 这几个参数值&#xff1a;改变颜色 wait / process / finish / error / --><!-- active 到第几个是绿色 --><el-steps :space&qu…...

038:mapboxGL 旋转地图(rotateTo)

第038个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中旋转地图。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共68行)相关API参考:专栏目标示例效果 配置方式 1)查看基础设置:https://xiaozhuan…...

java遇到的问题

java遇到的问题 Tomcat与JDK版本问题 当使用Tomcat10的版本用于springmvc借用浏览器调试时&#xff0c;使用JDK8浏览器会报异常。 需要JDK17&#xff08;可以配置多个JDK环境&#xff0c;切换使用&#xff09;才可以使用&#xff0c;配置为JAVA_HOME路径&#xff0c;否则&a…...

LLM(二)| LIMA:在1k高质量数据上微调LLaMA1-65B,性能超越ChatGPT

本文将介绍在Lit-GPT上使用LoRA微调LLaMA模型&#xff0c;并介绍如何自定义数据集进行微调其他开源LLM 监督指令微调&#xff08;Supervised Instruction Finetuning&#xff09; 什么是监督指令微调&#xff1f;为什么关注它&#xff1f; 目前大部分LLM都是decoder-only&…...

Android AMS——创建Application(七)

与在 App 内部启动一个 Activity 的不同之处在于,点击桌面 Launcher 首次启动一个应用程序的时候,会先去创建一个该应用程序对应的进程,然后执行 ActivityThread 的 main() 方法去创建该应用对应的 Application,然后再去启动首页 Activity。前面已经分析了进程的创建和启动…...

html 边缘融合加载

html 代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>边缘融合加载</title><style>* {margin: 0;padding: 0;box-sizing: border-box;}body {height: 100vh;padding-bottom: 80px;b…...

ElasticSearch - 在 微服务项目 中基于 RabbitMQ 实现 ES 和 MySQL 数据异步同步(考点)

目录 一、数据同步 1.1、什么是数据同步 1.2、解决数据同步面临的问题 1.3、解决办法 1.3.1、同步调用 1.3.2、异步通知&#xff08;推荐&#xff09; 1.3.3、监听 binlog 1.3、基于 RabbitMQ 实现数据同步 1.3.1、需求 1.3.2、在“酒店搜索服务”中 声明 exchange、…...

Springboot+vue的企业人事管理系统(有报告),Javaee项目,springboot vue前后端分离项目。

演示视频: Springbootvue的企业人事管理系统&#xff08;有报告&#xff09;&#xff0c;Javaee项目&#xff0c;springboot vue前后端分离项目。 项目介绍&#xff1a; 本文设计了一个基于Springbootvue的前后端分离的企业人事管理系统&#xff0c;采用M&#xff08;model&am…...

初识Java 11-1 函数式编程

目录 旧方式与新方式 lambda表达式 方法引用 Runnable 未绑定方法引用 构造器方法引用 函数式接口 带有更多参数的函数式接口 解决缺乏基本类型函数式接口的问题 本笔记参考自&#xff1a; 《On Java 中文版》 函数式编程语言的一个特点就是其处理代码片段的简易性&am…...

【Ambari】银河麒麟V10 ARM64架构_安装Ambari2.7.6HDP3.3.1问题总结

&#x1f341; 博主 "开着拖拉机回家"带您 Go to New World.✨&#x1f341; &#x1f984; 个人主页——&#x1f390;开着拖拉机回家_大数据运维-CSDN博客 &#x1f390;✨&#x1f341; &#x1fa81;&#x1f341; 希望本文能够给您带来一定的帮助&#x1f338;文…...

李宏毅机器学习第一课(结尾附作业模型详细分析)

机器学习就是让机器找一个函数f&#xff0c;这个函数f是通过计算机找出来的 如果参数少的话&#xff0c;我们可以使用暴搜&#xff0c;但是如果参数特别多的话&#xff0c;我们就要使用Gradient Descent Regression (输出的是一个scalar数值) Classification &#xff08;在…...

对日项目工作总结

从18年8月到23年中秋节&#xff0c;目前已经入职主营对日车载项目的公司满5年了&#xff0c;一般来说&#xff0c;在一家公司工作工作超过3年&#xff0c;如果是在比较大型以及流程规范的公司&#xff0c;那么该公司的工作流程&#xff0c;工作思维会深深地烙印在该员工的脑海中…...

设计模式探索:从理论到实践的编码示例 (软件设计师笔记)

&#x1f600;前言 设计模式&#xff0c;作为软件工程领域的核心概念之一&#xff0c;向我们展示了开发过程中面对的典型问题的经典解决方案。这些模式不仅帮助开发者创建更加结构化、模块化和可维护的代码&#xff0c;而且也促进了代码的复用性。通过这篇文章&#xff0c;我们…...

【内网穿透】在Ubuntu搭建Web小游戏网站,并将其发布到公网访问

目录 前言 1. 本地环境服务搭建 2. 局域网测试访问 3. 内网穿透 3.1 ubuntu本地安装cpolar 3.2 创建隧道 3.3 测试公网访问 4. 配置固定二级子域名 4.1 保留一个二级子域名 4.2 配置二级子域名 4.3 测试访问公网固定二级子域名 前言 网&#xff1a;我们通常说的是互…...

在cesuim上展示二维模型

前提问题&#xff1a;在cesuim上展示二维模型 解决过程&#xff1a; 1.获取或定义所需变量 2.通过window.cesium.viewer.imageryLayers.addImageryProvider和new Cesium.UrlTemplateImageryProvider进行建模 3.传入url路径后拼接{z}/{x}/{y}.png 4.聚焦到此模型window.ces…...

c/c++中如何输入pi

标准的 C/C 语言中没有π这个符号及常量&#xff0c;一般在开发过程中是通过开发人员自己定义这个常量的&#xff0c;最常见的方式是使用宏定义&#xff1a; 方法1&#xff1a;#define pi 3.1415926 方法2&#xff1a;使用反三角函数const double pi acos(-1.0);...

python爬虫:JavaScript 混淆、逆向技术

Python爬虫在面对JavaScript混淆和逆向技术时可能会遇到一些挑战&#xff0c;因为JavaScript混淆技术和逆向技术可以有效地阻止爬虫对网站内容的正常抓取。以下是一些应对这些挑战的方法&#xff1a; 分析网页源代码&#xff1a;首先&#xff0c;尝试分析网页的源代码&#xf…...

Vue error:0308010C:digital envelope routines::unsupported

vue项目&#xff0c;npm run dev的时候出现&#xff1a;Error: error:0308010C:digital envelope routines::unsupported vue项目&#xff0c;npm run dev的时候出现&#xff1a;Error: error:0308010C:digital envelope routines::unsupported 这个是node的版本问题。我的nod…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

raid存储技术

1. 存储技术概念 数据存储架构是对数据存储方式、存储设备及相关组件的组织和规划&#xff0c;涵盖存储系统的布局、数据存储策略等&#xff0c;它明确数据如何存储、管理与访问&#xff0c;为数据的安全、高效使用提供支撑。 由计算机中一组存储设备、控制部件和管理信息调度的…...