堆（二叉堆）堆是一棵完全二叉树，完全二叉树转换为顺序储存（数组）时不浪费储存空间，因此堆可以由数组储存。小顶堆：最小元在根节点，对于每一个节点x，x的父节点的值小于等于x的值。大顶堆：最大值在根节点，对于每一个节点x，x的值大于等于子节点的值。堆排序的实现方式就是使用堆这种数据结构。
插入节点：在可用位置（树的最下层最右侧节点的右侧，即数组的末尾）创建一个空穴，将空穴上移直到正确位置，称为上滤。
删除堆顶 由于根节点是最小元，删除最小元后需要将新的最小值作为根节点。因此在根节点中创建空穴，将空穴的左右节点的较小者放入空穴，那么空穴下移，循环操作，直至堆的最后一个节点（数组的最后一个元素）可以放入空穴。
实现 heap和priority_queue都是堆的实现形式，区别在于。priority_queue只能保持顺序，只能访问堆顶元素。heap可以访问任意成员，访问更自由。
头文件<algorithm> heap不是模板数据类型 而是将一个模板数据类型变成堆的储存顺序。根据上面的性质，堆最简单的储存形式是数组。操作有：创建堆（make_heap），插入节点（push_heap），删除堆顶（pop_heap）
make_heap(itr1,itr2,cmp);itr1迭代器开始，itr2迭代器结束的后一个，cmp比较函数。默认使用a<b生成大顶堆。自定义cmp函数使用a>b可生成小顶堆。这里与vector的sort函数相反。sort使用<生成升序，使用>生成降序。当使用了自定义函数时，所有对堆的操作也要使用该自定义函数。
push_heap() push_heap(itr1，itr2，cmp)将新插入的节点放到堆的合适位置上。默认新加入的节点在数组尾。将数组尾的元素放到数组的合适位置上。
pop_heap() 将数组首（堆顶）元素放到数组尾 再删除数组尾元素即可删除堆顶。
头文件<queue> 名称空间std 声明priority_queue<type1,tyep2,cmp> type1是元素类型，如int；type2是储存元素的类型，如vector<int>,cmp是计较函数。若使用默认greater和less需包含头文件<functional>。priority_queue中元素总是有序的，且只能访问堆顶元素。
.push() 插入元素 .pop()删除堆顶元素 .size()堆中节点个数 .top()堆顶元素 .empty()堆是否空
题目：Leetcode 703. Kth Largest Element in a Stream https://leetcode.com/problems/kth-largest-element-in-a-stream/ 源代码github：https://github.com/AnkangH/LeetCode/blob/master/数据结构/栈和队列/703. Kth Largest Element in a Stream.cpp 题目：设计一个类，包括一个初始化函数和add函数，每次调用add函数都返回当前所有输入数字中第k大的数字。 解析：要求第k大的数字，假设初始化时第k大的数字为s(k)，那么初始化时数组中所有小于s(k)的数字都不会对之后的s(k)有影响，同理，add数字时，比当前s(k)小的数值也不会对之后的s(k)造成影响。 因此首先想到的是维持一个大小为k的递减数组，每次增加新数字时，如果比s(k)大，那么放入数组排序，删除最小的数字之后，数组末尾的元素即是所有输入中第k大的数字。但是这样会造成初始化以及有大于数组末尾元素输入时，对需要对数组重新排序，当k较小时，如果初始化输入的数组较大，那么时间复杂度会很大，当k较大时，无论是初始化还是比较之后的输入，都会消耗大量的时间在数组排序上。 解决办法是利用堆（优先队列），维持一个大小为k的小顶堆，对于每个新输入，如果数字大于堆顶数字，就将其加入堆中，并删除堆顶元素，新的堆顶元素就是输入流中的第k大元素，否则堆顶元素是第k大数字。需注意，初始化时数组的长度length>=k-1，当length=k-1时，此时数组中没有第k大数字，第一次add之后才有。因此这里用一个标志位flag，记录初始化时是否有第k大元素，即堆的大小是否为k。
class KthLargest { priority_queue<int,vector<int>, greater<> > qMin;//维持一个大小为k的小顶堆 顶堆为第k大元素 int flag=0;//标志初始化时，数组是否存在第k大元素 public: KthLargest(int k, vector<int>& nums) { int size=nums.size(); if(size>k-1)//初始化时 数组存在第k大元素 { for(int i=0;i<size;i++) { if(i<=k-1)//arr[0]-arr[k-1]共k个值 qMin.push(nums[i]);//前k个元素入堆 else//当k的大小为k值，保证堆的大小为k { qMin.push(nums[i]); qMin.pop(); } } flag=1; } else//若初始化时，数组元素数目少，此时不存在第k大元素 数组元素全部入堆 for(int i=0;i<size;i++) qMin.push(nums[i]); } int add(int val) { if(flag==0)//初始化时，不存在第k大元素，即堆的大小不为k { qMin.push(val); flag=1; } else//否则 维持堆的大小为k { qMin.push(val); qMin.pop(); } return qMin.top();//返回堆顶元素即可 } };
