find-median-from-data-stream & multiset priority queue 堆
2024-08-31 03:37:41
https://leetcode.com/problems/find-median-from-data-stream/
这道题目实在是不错,所以单独拎出来。
https://discuss.leetcode.com/topic/27521/short-simple-java-c-python-o-log-n-o-1/2
看这里面的C++解法,用了priority_queue来实现的。(其实也是堆,之前我一直用multiset)
而Java用的PriorityQueue来做。
关于multiset 和 priority queue的区别,可以看这里:
https://discuss.leetcode.com/topic/27521/short-simple-java-c-python-o-log-n-o-1/2
priority_queue 调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现。
注意,priority queue默认是大顶堆,top()和pop()都是针对最大的元素。
而Java的PriorityQueue是从小到大排的。
注意下面对于比较方法的初始化(尤其是比较方式参数的传入)
// constructing priority queues
#include <iostream> // std::cout
#include <queue> // std::priority_queue
#include <vector> // std::vector
#include <functional> // std::greater class mycomparison
{
bool reverse;
public:
mycomparison(const bool& revparam=false)
{reverse=revparam;}
bool operator() (const int& lhs, const int&rhs) const
{
if (reverse) return (lhs>rhs);
else return (lhs<rhs);
}
}; int main ()
{
int myints[]= {,,,}; std::priority_queue<int> first;
std::priority_queue<int> second (myints,myints+);
std::priority_queue<int, std::vector<int>, std::greater<int> >
third (myints,myints+);
// using mycomparison:
typedef std::priority_queue<int,std::vector<int>,mycomparison> mypq_type; mypq_type fourth; // less-than comparison
mypq_type fifth (mycomparison(true)); // greater-than comparison return ;
}
最新文章
- Java多线程系列--“JUC集合”03之 CopyOnWriteArraySet
- 区别和详解:js中call()和apply()的用法
- 前端MVC学习总结(四)——NodeJS+MongoDB+AngularJS+Bootstrap书店示例
- WordPress无法连接MySQL数据库
- HTML的定位属性
- $ is not defined错误类型
- Chapter12:动态内存
- Hadoop on Mac with IntelliJ IDEA - 1 解决input path does not exist问题
- Redirect
- Bootstrap插件的使用
- winform模拟鼠标按键
- Unity3D基础学习 NGUI Example 7-Scroll View(Panel)制作固定包裹栏,点击传递参数显示物体
- Delphi 的动态数组
- codeforces 463E . Caisa and Tree
- 《JS权威指南学习总结--8.8 函数式编程和8.8.1使用函数处理数组》
- Java基础(四)-异常处理机制及其设计
- NYoj_20吝啬的国度
- ●POJ 3378 Crazy Thairs
- 苹果手机对网页上样式为position:fixed的弹窗支持不好的解决办法
- 【Teradata SQL】创建数据库和表