接上篇 Java集合与数据结构——优先级队列（堆） 一、对象比较的方法 上节课我们讲了优先级队列，优先级队列在插入元素时有个要求： 插入的元素不能是null或者元素之间必须要能够进行比较，...为了简单起见，我们只是插入了Integer类型，那优先级队列中能否插入自定义类型对象呢？ ...我们先不用优先级队列来比较，先来看自定义类型如何进行比较… ? 我们写了一个 Student 的一个类，类内部有姓名和年龄两个属性，我们直接通过数组类进行比较… 我们来看结果 ? ...那么我们一个自定义类型中有两个属性甚至多个属性的情况下，如何进行比较呢？...用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法。 ?
，不过优先级队列 priority_queue 中加入了 泛型编程 的思想，并且属于 STL 中的一部分 这就是一个堆，最顶上的石头 优先级最高 或 优先级最低 ---- ️正文 1、优先级队列的使用...首先需要认识一下优先级队列 priority_queue 1.1、基本功能 优先级队列的构造方式有两种：直接构造一个空对象 和 通过迭代器区间进行构造 直接构造一个空对象 #include <...} 注意： 默认比较方式为 less，最终为 优先级高的值排在上面（大堆） 通过迭代器区间构造对象 #include #include #include...= last) { push(*first); first++; } } 测试： 2.2、基本功能 因为是容器适配器，所以优先级队列也没有迭代器 同时基本功能也比较少，首先来看看比较简单的容量相关函数...//优先级队列的大小（有效元素数） size_t size() const { return _con.size(); } 获取堆顶元素：堆顶元素即第一个元素（完全二叉树的根） //堆顶元素（优先级最
[first, last)的元素 empty() 检测优先级队列是否为空，是返回true，否则返回false top() 返回优先级队列中最大（最小）元素，即堆顶元素 push(x) 在优先级队列中插入元素...是元素类型，Container是底层容器类型（默认为vector），Compare是元素比较的函数对象类型（默认为std::less，用于最大堆）。...priority_queue(first, last)：使用范围为[first, last)的迭代器构造一个优先队列。 默认行为： 默认情况下，优先队列是最大堆，即最大元素位于堆顶。...可以通过自定义比较函数对象来改变这一行为，从而创建最小堆或者基于自定义的优先级规则进行排序。...函数对象通常用于STL中的算法、容器和适配器中，它们可以作为参数传递给算法，用于自定义排序、查找、比较等操作。
，接下来就说一说什么是仿函数： 前面我们知道加入了仿函数参数将默认建大堆改为了建小堆，而建大堆和建小堆的代码唯一的区别就在于向上调整算法和向下调整算法当中的比较符号的改变，那么我们怎么可以让它可以灵活改变呢...中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。...Date(2021,12,24)); pq.push(Date(2022,11,24)); cout<<pq.top()<<endl; pq.pop(); //选出最大 return 0; } 当我们优先级队列使用自定义类型时...因为push和pop操作会调用仿函数类的重载函数，该重载函数进行比较时，默认是不支持自定义类型比较的，所以需要重载 我们还可以这样玩：当传的时Date*时，用less仿函数会有问题： int main...因为我们的数据类型为指针，仿函数类型的重载函数比较的是地址大小，所以会出问题 这是一种仿函数的变异玩法，我们可以控制仿函数比较方式我们需要另外写个仿函数： class PDateLess { public
，对应得代码也有些许差异，但为了减少代码的量，提高程序员编程的效率，我们就可以在上述优先级队列的类模板中再传入一个仿函数，对于不同的堆传不同的仿函数类以实现不同的需求； 模板不能直接传入函数，但是可以传类型...，可以是自定义类型也可以是内置类型，所以可以传入一个仿函数（它本质是一个类） 4.优先级队列模拟实现 优先级队列模拟实现和队列类似，所不同的是每次插入数据后都会使用算法将队列中的数据调整为一个堆，每次删除也是删除堆顶元素...，大家可以依照堆的向下调整自己试试看写一下大堆的向上调整 ✨仿函数 有了堆向下调整算法来删除堆顶元素和建堆，以及堆向上调整算法尾插元素，我们就可以实现优先级队列了 但是优先级队列能否按照我们需要选择大堆还是小堆呢...，为了和STL库里面的命名保持一致，我们使用Less建立大堆，Greater建立小堆，因为建大堆还是小堆关键就在于父节点与孩子节点比较是大于还是小于，所以我们将所有比较的地方都使用仿函数，这样就可以按照我们希望的方式来比较...，如果希望是大堆，就按Less中的来比较 这样就可以将上述仿函数传给优先级队列了： //优先级队列的模拟实现 template<class T,
优先级队列实际就是数据结构初阶所学的堆，堆的本质就是优先级，父节点比子节点大就是大堆，父节点比子节点小就是小堆，这其实就是优先级队列。...我们可以直接利用优先级队列的结构特点，先利用vector的迭代器区间构造一个默认是大堆的优先级队列，然后依次pop k-1次堆顶的数据，最后的堆顶数据就是第K个最大的元素，直接返回即可。...在优先级队列中增加仿函数也是比较简单的，具体的逻辑和前面所说的冒泡排序实际是差不多的，唯一不同的是，冒泡排序那里是函数模板，对于函数模板所传参数是仿函数实例化出来的对象，或者是函数指针类型定义出来的指针变量...但是当优先级队列存储的数据不再是日期类对象，而是日期类对象的地址时，那在优先级队列内部比较的时候，就不再是比较日期了，而变成比较地址的大小了，但是各个对象之间的地址又没有关系，这个时候原有的仿函数无法满足我们的要求了...，需要用户在自定义类型中提供<的重载 priority_queue q1; q1.push(Date(2018, 10, 29));//让优先级队列存储日期类的匿名构造 q1.push
就比如我们这里优先级队列控制这个大堆小堆，我们之前实现过堆，我们知道控制大堆小堆其实就是就是控制里面元素的比较方式不同。...而我们刚才这样写的是只针对整型，如果像比较任意类型我们就可以将他实现成模板： 1.2.2 在OJ中的使用：数组中的第K个最大元素 下面我们来看一个题：数组中的第K个最大元素 思路1：排序 那这道题我们最容易想到的方法应该就是堆数组排个序...那现在呢，我想用我们的priority_queue（优先级队列）去存我们的自定义类型数据——日期类的变量，可以吗？...所以： 如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载 4...._day; return _cout; } //int main() //{ // 大堆，需要用户在自定义类型中提供<的重载 // //yin::priority_queue q1;
Williams在1964年发表的堆排序，当时他提出了二叉堆树作为此算法的数据结构，堆在戴克斯特拉算法和带优先级队列中亦为重要的关键。...优先队列至少需要支持下述操作： a.插入带优先级的元素 b.取出具有最高优先级的元素 c.查看最高优先级的元素。 综合考虑插入和删除的性能 优先队列一般采用堆来实现。...3.3 优先队列的自定义优先级 模板化的优先队列扩展了使用场景，但是也产生了新的问题，就是默认的优先级比较函数不一定满足所有要求，因此很多时候都需要自己来定义优先级判定函数。...实现了一个模板优先队列需要三个参数： 容器元素的类型 存储数据所用的容器 比较函数 缺省情况是less #include // 队列和优先队列的声明 std::queue pq;...可以认为优先队列是对堆的工具化封装，加上模板和自定义比较函数两个利器加持，优先队列让使用者不再苦于堆排序的原始造轮子。
，因为我们每次在向优先队列中添加新元素时，都需要对优先队列中所有元素的优先级进行对比，然后添加到按优先级排序中的位置。...当我们使用数组表示最大堆时，我们可以使用在常见的线性结构中自定义的动态数组，这样我们在向堆中添加和删除元素时，我们就可以动态地改变数组的容量，不需要考虑数组容量的问题了。.../** * 基于二叉最大堆的性质：堆中某个节点的值总是不大于其父节点的值 * @param 二叉最大堆中的元素必须要具有可比较性 */ public class MaxHeap<E extends...在heapify代码实现之前，我们需要在实现的动态数组中添加一个构造器，该构造器可以将传入的数组转为动态数组。...，对与100万个整数这种数据量来说，O(nlogn)和O(n)这两种时间复杂度所花费的时间差不多： 基于堆实现优先队列 这里是基于自定义的最大堆进行实现的优先队列，元素值越大，优先级越高，具体代码实现如下
仿函数的特点 1.仿函数即使定义相同，也可能有不同的类型； 2.仿函数通常比一般函数速度快； 3.仿函数使程序代码变简单。... Le; cout << Le(a, b) << endl; //像函数一样调用 return 0; } 二.模拟实现priority_queue priority_queue即优先级队列...，它的底层是一个堆，且默认是大堆，所以在模拟实现优先级队列时要先建堆，不了解的话可以参考文章：堆的实现 相关接口： 源码 //less是库里的仿函数， 用来判断左操作数是否小于右操作数，可以用来建大堆...//greater也是库里的仿函数，比较左操作数是否大于右操作数，可以用来建小堆 //库里比较的是内置类型的大小，如果是自定义类型，那么自定义类型里就必须要重载 > 或 < 运算符 template<...之前在C语言那里的时候，还得自己造轮子，手搓一个堆出来，但是C++不用了，直接使用优先级队列priority_queue class Solution { public: int findKthLargest
大家好，又见面了，我是你们的朋友全栈君。 学过数据结构的人应该对Queue 队列很熟悉了，队列是一种先进先出(FIFO)的数据结构，所以它出队列的优先级就是进入队列的次序。...但我们有时候需要其它的优先级，很多高级语言都会提供带优先级的队列，在Java中就是PriorityQueue了，今天我们来看下PriorityQueue的使用和实现。...，其它类型或者其它优先级需要传入自定义comparator。...取最大堆的最大值 按最大堆的性质，根节点是最大的，取完后按删除的方法删掉跟节点就行了。...，就是上文中或者最大堆中最大值的方式。
),需要支持随机访问迭代器，以便始终在内部保持堆结构 一、使用 在有了前面容器使用的基础之下，我们对于优先级队列priority_queue的使用成本不是很大，值得注意的是头文件为 普通的队列是先进先出...，优先级队列默认是优先级高的先出 Container:优先级队列默认使用vector作为其底层存储数据的容器，支持[]的使用，支持随机访问，在vector上又使用了堆算法将vector中元素构造成堆的结构...构造函数 接口 查看文档的接口 常用接口 函数声明 接口说明 priority_queue()/priority_queue(first, last) 构造一个空的优先级队列 empty( ) 检测优先级队列是否为空...自定义类型 这里的比较大小是比较常见的，如果是自定义类型： 比如日期类，那该如何去进行大小的比较？一种是重载大小的比较运算符，使之支持日期类的大小比较。...：自定义类型会调用自己的迭代器区间构造，所以我们并不需要一个一个push，走个初始化列表即可，同时，数据进去之后我们还要建堆，利用向下调整算法：从倒数第一个非叶子节点，既最后一个节点的父节点开始进行向下调整
empty(): 检查队列是否为空 priority_queue的特点: 它是一个容器类模板，可以存储任何可比较的类型。 该容器中的元素按照一定的比较规则（默认为大根堆）排列，允许用户自定义规则。...这里的优先级队列就是一个堆的结构. void test1() { //构造1: priority_queue pq1;//创建一个空优先级队列 默认是大堆 //向优先级队列中插入一些数据...所以不难得出,大堆是排序是降序. 2.2 利用优先级队列排序(升序) 通过观察源码,我们不难发现,优先级队列有三个模板参数,其中后两个是某仍给出的....: 前面说了,优先级队列就是堆,那么堆的算法中,元素的比较方法会决定是大堆还是小堆....(当然,也可以不写,因为会默认调用) (2)迭代器区间构造 将迭代器区间的值依次插入(push())进优先级队列. (2) push() 将数据先尾插进容器.
学过数据结构的人应该对Queue 队列很熟悉了，队列是一种先进先出(FIFO)的数据结构，所以它出队列的优先级就是进入队列的次序。...但我们有时候需要其它的优先级，很多高级语言都会提供带优先级的队列，在Java中就是PriorityQueue了，今天我们来看下PriorityQueue的使用和实现。...，其它类型或者其它优先级需要传入自定义comparator。...取最大堆的最大值 按最大堆的性质，根节点是最大的，取完后按删除的方法删掉跟节点就行了。 ...，就是上文中或者最大堆中最大值的方式。
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素) 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素...二. priority_queue的使用 优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆...，用户需要在自定义类型中提供> 或者< 的重载。...sizeof(a) / sizeof(int); i++) { cout << a[i] << " "; } return 0; } 四.priority_queue模拟实现 既然已经知道优先级队列中的仿函数的相关知识...，需要用户在自定义类型中提供<的重载 priority_queue q1; q1.push(Date(2018, 10, 29)); q1.push(Date(2018, 10, 28
十几天没有更新自己的博客了，因为目前在算法和数据结构的学习中，碰到了一些问题，例如之前就在优先队列，堆这个数据结构面前，感觉到有点吃不透概念，而使用的那本书上写的实在太抽象了，所以又查找了很多资料，最终对优先队列这个数据结构有了一定的了解...花了点时间才啃下来的知识，当然要把它记录下来了，所以今天就来回顾一下优先队列。 优先队列也是一种抽象数据类型。优先队列中的每个元素都有各自的优先级。这个概念其实打几个比方会理解的比较快一点。...比如我们人人都用过的windows系统，当我们打开任务管理器的时候，每个任务的优先级别是不同的，而操作系统会选择优先级别最高的任务先执行，同时我们也能在选项里标记任务的优先级。...优先队列也是一个道理，优先处理优先级别高的数据或者任务。 优先级最高的元素最先得到服务，优先级别相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。...优先队列至少要支持这些操作： 插入带优先级的元素。 取出具有最高优先级的元素。 查看最高优先级的元素。
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。...注意：默认情况下priority_queue是大堆 构造函数 有关这些参数的使用我们后文进行详细讲解，创建一个优先级队列： priority_queue pq; empty(...) 检测优先级队列是否为空，是返回true，否则返回false top( ) 返回优先级队列中最大(最小元素)，即堆顶元素 push( ) 在优先级队列中插入元素x pop( ) 删除优先级队列中最大...默认是 std::less，该函数使得最大的元素被认为是最高优先级（形成最大堆）。...如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载 class Date { public: Date(int year = 1900, int month
last) 构造一个空的优先级队列 empty( ) 检测优先级队列是否为空，是返回true，否则返回 false top( ) 返回优先级队列中最大(最小元素)，即堆顶元素 push(x) 在优先级队列中插入元素...q2.empty()) { cout << q2.top() << " "; q2.pop(); }cout << endl; } 结果： 注意：如果在priority_queue中放自定义类型的数据...，用户需要在自定义类型中提供> 或者< 的重载 示例： class Date { public: Date(int year = 1900, int month = 1, int day = 1)...，需要用户在自定义类型中提供<的重载 priority_queue q1; q1.push(Date(2021, 10, 19)); q1.push(Date(2021, 10, 29...，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂 示图： 迭代器如何维护空间： 总结 优势： 与vector比较，deque头部插入和删除时
// 这里定义的优先级高的意思，是频次低的优先级高， 52 // 对于优先队列，底层虽然是最大堆，取出优先级高的那个元素，但是这个优先级最高的这个元素是频次最低的那个元素...86 // 此时，求出，前k个频数最高的元素 87 // 由于此时，优先队列承载的元素类型是什么类型呢，此时map是键值对的形式 88 // 要依据元素所对应的频类来决定优先级...，可以自定义比较器的方式进行实现。...，比较器 35 // 如果优先队列里面存储的就是字符串，java默认字符串大小比较是按照字典序进行比较的， 36 // 如果有一个自定义的字符串比较的方案，由于不能修改Java中字符串比较的方法的...，比较器 35 // 如果优先队列里面存储的就是字符串，java默认字符串大小比较是按照字典序进行比较的， 36 // 如果有一个自定义的字符串比较的方案，由于不能修改Java中字符串比较的方法的
优先队列 优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。...和堆的区别 优先队列是一种抽象的数据类型，而堆就是具体的数据结构。也就是说，堆是优先队列的实现之一。 堆 堆是一种特别的二叉树，需要满足以下两个性质才能称为堆。...完全二叉树 父节点的值始终大于等于或小于等于子节点的值 堆的分类 最大堆/大根堆 最大值是根节点 最小堆/小根堆 最小值是根节点 堆操作的复杂度 堆的常用方法 小根堆创建...PriorityQueue(); 大根堆创建 PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); 创建带初始值的...最大堆排序算法步骤如下： 将所有元素堆化成一个最大堆； 取出并删除堆顶元素，并将该堆顶元素放置在存储有序元素的数据集T中； 此时，堆 会调整成新的 最大堆； 重复 3 和 4 步骤，直到堆中没有元素；
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
