Heap是一种数据结构能保证取max/min是O(1)时间。通常如果查最小值/最大值我们可以用Heap。如果是查是不是存在(Contain())就用HashMap。如果又要查最小/大值又要查是不是存在就用HeapHashMap.Max-heap/Min-heap保证父节点都比子节点大/小但兄弟节点之间没有大小关系。Heap虽然是一个(满)二叉树但通常用数组实现因为容易实现。一个节点i的左子节点编号是2*i右子节点是2*i1。Heap通常是完全二叉树(因为效率高)但没有要求一定是完全二叉树。Heap Sort就是把所有元素放到Max Heap或Min Heap里面再一个一个pop出来。时间复杂度最坏/最好/平均 都是O(nlogn)空间复杂度为O(1)。注意Heap Sort是不稳定排序因为它不能保证重复元素排序后还保留前后一致的顺序。注意Heap Sort实际应用不多为什么呢因为Heap的维护很麻烦。实际场景中的数据是频繁发生变动的而对于待排序序列的每次更新增删改我们都要重新做一遍堆的维护以保证其特性(父节点大/小于其子节点)这在大多数情况下都是没有必要的。另一个原因是Heap的cache locality不好即如果在较短时间内访问多个元素这多个元素在Heap中的位置可能较远所以不能用cache一次读出来。当数据更新不很频繁的时候堆排序可能会比较实用。Priority Queue也是一种数据结构。其中每个元素都有一个关键字key元素之间的比较都是通过key来比较的。优先队列包括最大优先队列和最小优先队列优先队列的应用比较广泛比如作业系统中的调度程序当一个作业完成后需要在所有等待调度的作业中选择一个优先级最高的作业来执行并且也可以添加一个新的作业到作业的优先队列中。一个典型的例子是实时输出最近的一个小时内访问频率最高的10个IP 。注意这里是实时输出也就是说Priority Queue/Heap可以用于在线算法不需要读完全部的数据可以real time输出到当前为止的结果。Priority Queue可以用Heap实现也可以用其他方式比如说直接对数组插入实现但是效率不高。注意Priority Queue不是Queue那为什么它的名字里面有queue呢可能是因为它能提供queue的接口比如remove()pop() insert(), top()等等。Priority Queue和Heap有什么区别吗如果是JAV自带的Priority Queue的话答案是有的(C的Priority Queue可能也类似具体要确认一下。具体的区别是在remove操作中Priority Queue的时间复杂度是O(n)而Heap是O(logn)。因为Priority Queue需要找到这个数据需要O(n)的时间而Heap借助了HashMap所以只需要O(1)的时间就可以找到。那为什么Priority Queue不用HashMap呢这个就是JAVA提供的函数里面没有加上这一块而已如果自己编程就也可以是O(logn)。C的priority_queue的定义是priority_queueType, Container, FunctionalType为数据类型 Container为保存数据的容器Functional为元素比较方式。如果不写后两个参数那么容器默认用的是vector比较方式默认用operator也就是优先队列是大顶堆队头元素最大。下面的内容参考了链接https://blog.csdn.net/nisxiya/article/details/45725857另外需要注意的是C STL默认的priority_queue是将优先级最大的放在队列最前面也即是最大堆。假设有如下一个structstruct Node { int value; int idx; Node (int v, int i): value(v), idx(i) {} friend bool operator (const struct Node n1, const struct Node n2) ; }; inline bool operator (const struct Node n1, const struct Node n2) { return n1.value n2.value; } priority_queueNode pq; // 此时pq为最大堆如果需要最小堆则需要如下实现struct Node { int value; int idx; Node (int v, int i): value(v), idx(i) {} // friend bool operator (const struct Node n1, const struct Node n2) ; friend bool operator (const struct Node n1, const struct Node n2) ; }; inline bool operator (const struct Node n1, const struct Node n2) { return n1.value n2.value; } priority_queue Node, vector Node , greater Node pq; // 此时greater会调用 方法来确认Node的顺序此时pq是最小堆 注意为什么greater是最小堆呢而less是最大堆呢因为如果是greater的时候说明大的会沉下去所以是最小堆。如果是less priority_queueint, vectorint, greaterint minHeap; priority_queueint, vectorint, lessint maxHeap;也可以用以下办法定义最小堆class Node { public: Node(int r, int c, int v) : row(r), col(c), val(v) {} bool operator (const Node obj) const { return val obj.val; } int row, col, val; }; priority_queueNode pq;注意我们什么时候需要定义operator和operator呢这里要注意最小堆需要跟top比比top大的才能进堆所以需要定义operator同理最大堆需要定义operator。但如果这里我们不用自定义类型(比如Node)的话我们就不需要定义operator和operator了因为C可以直接对内部保留类型如int, char)来比大小。也可以用decltype来定义最大堆和最小堆。以最小堆为例mapint,intfreqs;//num, freqintnnums.size();for(inti0;in;i){freqs[nums[i]];}autocomp[](inta,intb){returnfreqs[a]freqs[b];};priority_queueint,vectorint,decltype(comp)minHeap(comp);记忆捷径把 return a b 翻译成“排序”如果你觉得底层的堆推导很绕可以用 std::sort 的逆向思维来记忆在 std::sort 中如果你传入 a b代码会按从大到小降序排列大元素在前面。std::priority_queue 的堆顶对应的是底层数组的“末尾”因为为了效率pop 操作是从数组末尾移除元素的。如果数组是从大到小排列大…中…小那么末尾就是最小的元素。既然末尾是最小的元素而堆顶对应的就是末尾那么堆顶自然就是最小的元素小顶堆。末尾是最小的元素而堆顶对应的就是末尾。为什么? 这是一个非常硬核且底层的 C 标准库STL实现细节。简单直接的答案是为了实现 (O(1)) 时间复杂度的删除Pop操作。如果堆顶对应数组的开头索引 0删除堆顶时就需要移动数组中的所有其他元素这会导致性能暴跌。为了避免这个性能问题C STL 的 std::priority_queue 巧妙地利用了 std::vector 的末尾。注意sort()和priority_queue 的第3个参数不一样sort不用加decltyppriority_queue要加。它们两个的第三个参数本质完全不同std::sort 是一个函数Function它的第三个参数需要传入一个对象 / 实例可调用对象。std::priority_queue 是一个类模板Class Template它的第三个参数需要传入一个类型Type。这就是为什么一个不需要 decltype而另一个必须要加或者传入结构体的原因。另外一个诀窍关于记住第3个参数到底是类型type还是实例。container(e.g., map, set, queue, priority_queue, vector, …) 的第3个参数是type; function(e.g., sort)的第3个参数是function。看符号尖括号 如 map…, unordered_map…, priority_queue…里面一律填 类型Type。圆括号 ( )如 sort(…), find_if(…)里面一律填 对象/值Object/Value。如果硬要用 Lambda传给尖括号 必须写 decltype(your_lambda)C20 之前。传给圆括号 ( )直接写 your_lambda 名字或者把 { … } 丢进去即可。/////////////////////std::priority_queue类模板传类型当你声明一个优先队列时你是在定义一个变量创建对象。在 C 中定义变量时尖括号 里面填写的必须是编译期就能确定的“类型”。正确写法第三个参数是仿函数的“类型”priority_queueint,vectorint,greaterintpq;priority_queue 内部会根据你传入的类型 greater在自己类里面实例化出一个该类型的成员变量。在后续调用 push 等操作时它会在底层自己调用这个成员变量。如果你想用 Lambda 函数也必须像 unordered_map 一样使用 decltype 来获取其类型并且还要把 Lambda 对象传给构造函数autocmp[](inta,intb){returnab;};// 尖括号内填类型小括号内填对象priority_queueint, vector, decltype(cmp) pq(cmp);std::sort函数模板传对象当你使用 std::sort 时你是在执行一个具体的操作调用函数。函数的圆括号 ( ) 里面填写的必须是运行期的“对象、变量或临时值”。vectorintnums{3,1,4};// 正确写法 1传入一个临时的仿函数“对象”注意后面的小括号 {} 或 ()sort(nums.begin(),nums.end(),greaterint{});// 正确写法 2直接传入一个 Lambda 函数“对象”sort(nums.begin(),nums.end(),[](inta,intb){returnab;});std::sort 的第三个参数是一个可调用对象。编译器会通过自动类型推导Template Argument Deduction自己去识别你传进来的对象的类型不需要你在尖括号里手动指定。//////////////////////////////////////////////////一个经典的用最大堆和最小堆的例子是求n个无序数中的第K大的数。该题用最大堆和最小堆都可以做 重要。用最大堆做的代码如下。复杂度O(nlogn)// max-heap int findKthLargest(vectorint nums, int k) { priority_queueint pq(nums.begin(), nums.end()); for (int i 0; i k - 1; i) { pq.pop(); } return pq.top(); }用最小堆做代码如下。复杂度O(nlogk)// min-heap int findKthLargest(vectorint nums, int k) { priority_queueint, vectorint, greaterint pq; for (int i 0; i nums.size(); i) { if (pq.size() k) { int x pq.top(); if (nums[i] x) { pq.pop(); pq.push(nums[i]); } } else { pq.push(nums[i]); } } return pq.top(); } };当然也可以用将乘以负数的办法来构造最小堆。比如要构造一个int类型的最小堆priority_queue pq; //pq.push( -1 * v1) ; //pq.push( -1 * v2) ; //pq.push( -1 * v3) ; // 分别是插入v1, v2, v3变量的相反数那么pq其实也就变相成为了最小堆下面这个链接很不错https://blog.csdn.net/txl199106/article/details/44588487另外也可以通过定义struct cmp来实现最小堆cmp里面只需给出operator()函数。给出operator()后则不需再定义operator 或operator 。用这种方法必须通过以下方式定义priority_queue。priority_queueNode,vectorNode,cmpq;注意priority_queue第3个参数cmp必须是class/struct,而sort()的第3个参数可以是function或class/struct的实例(注意是实例不是class/struct的定义)。举例如下(定义最小堆)。如果要生成最大堆只需将operator()里面的改成即可。struct node{ int idx; int key; node(int a0, int b0):idx(a), key(b){} }; struct cmp{ bool operator()(node a, node b){ return a.key b.key; } }; priority_queuenode, vectornode, cmp q;实例代码如下 (from https://blog.csdn.net/txl199106/article/details/44588487)#include iostream #include queue using namespace std; struct Node{ int x, y; }node; struct cmp{ bool operator()(Node a,Node b){ if(a.xb.x) return a.yb.y; return a.xb.x;} }; int main(){ priority_queueNode,vectorNode,cmpq; for(int i0;i10;i){ node.xi; node.y10-i/2; q.push(node); } while(!q.empty()){ coutq.top().x q.top().yendl; q.pop(); } return 0; }该代码输出如下0 101 102 93 94 85 86 77 78 69 6如果将operator()里面的改为则为最大堆。输出结果为9 68 67 76 75 84 83 92 91 100 10另外C里面也可以用multiset实现最大堆和最小堆。代码如下multisetint,greaterintgreaterSet;multisetint,lessintlessSet;multisetintdefaultSet;//默认为lessSet将元素插入堆后greaterSet.begin()所指向的值就是最大值。lessSet.begin()所指向的值就是最小值。一个小总结 (不一定对)求第K大用最小堆:求第K小用最大堆这个好像不管是对动态数据和静态数据都实用时间复杂度O(nlogk)。但静态数据求第k大/小用quickselect更好时间复杂度O(n)。注意堆是完全二叉树但不是平衡二叉树。为什么不是平衡二叉树呢堆的左右两个子树的高度差的绝对值不超过1啊因为平衡二叉树必须首先是binary search tree堆不满足这个条件。另外下面这个链接解释了为什么sort和priority_queue的第三个参数不一样sort是传入一个Compare类的实例而priority_queue是传入一个类。这是因为本质上:sort是一个函数函数参数列表()中需要传入实例化后的具体对象;priority_queue是一个模板类模板的类型参数表中需要传入具体的类而不是对象。https://www.codenong.com/cs109745348/