LeetCode 295. Find Median from Data Stream

题目大意是给定一个int数据流,判断当前整个数组的中位数值。由于数据流是可以不断增加的,因此采用两个堆(最大堆*1+最小堆*1)来实现。

这东西思路网上都有,每次新进一个数,维护堆就行了。维护一次的复杂度是O(logN),对应整个数组的复杂度是O(N logN)

STL 堆相关的三个函数 make_heap(), push_heap(), pop_heap()

STL是个好东西,在<algorithm>库里面就有三个与堆有关的函数,利用vector存储堆元素就可以调用这些函数来建立、更新堆。

make_heap(first, last, comp)是建立堆的函数,输入的first, last对应begin()和end()的iterator,comp函数可选,与库中sort()用到的方法相同,自定义的时候比较两个元素x, y的偏序关系,返回true说明x应该排在前面。相关的有两个仿函数叫less<T>() 和greater<T>(),直接用来比较<和>关系的。

push_heap(first, last, comp)使用时,将新元素放在数组末尾(代表堆的末叶节点),然后调用这个函数更新堆,是一个sift-up的过程。

pop_heap(first, last, comp)会将堆顶元素调整到数组末尾用于pop,同时调整更新堆。

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注