【对顶堆优先队列】295. 数据流的中位数

本文涉及知识点

对顶堆优先队列

LeetCode295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:
MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10^-5 以内的答案将被接受。
示例 1：
输入
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
提示:
-10⁵ <= num <= 10⁵
在调用 findMedian 之前，数据结构中至少有一个元素
最多 5 * 10⁴ 次调用 addNum 和 findMedian

对顶堆

大根堆存放一半的小数，小根堆存放一半的大数。
由于只有增加，没有删除。我们往存放大数的堆中增加。再调整大小。
如果大数的数量大于小数的数量，则大数出堆到小数。
如果数据的数量是偶数，则最终大数堆和小数堆数量相等。
如果数据的数量是奇数，则最终大数堆比小数堆数量少1。
寻找中位数逻辑：
如果两个数堆的数量相等，返回堆顶的平均值。
否则返回小数堆的堆顶元素。

代码

核心代码

class MedianFinder {
public:
	MedianFinder() {

	}

	void addNum(int num) {
		m_heapBig.emplace(num);		
		if (m_heapBig.size() > m_heapSmall.size()) {
			m_heapSmall.emplace(m_heapBig.top());
			m_heapBig.pop();
		}
		while (m_heapBig.size() && m_heapSmall.size() && (m_heapBig.top() < m_heapSmall.top()))
		{
			const int s1 = m_heapSmall.top();
			const int b1 = m_heapBig.top();
			m_heapSmall.pop();
			m_heapBig.pop();
			m_heapSmall.emplace(b1);
			m_heapBig.emplace(s1);
		}
	}

	double findMedian() {
		if (m_heapSmall.size() == m_heapBig.size()) {
			return (m_heapSmall.top() + m_heapBig.top()) / 2.0;
		}
		return m_heapSmall.top();
	}
	priority_queue<int> m_heapSmall;
	priority_queue<int,vector<int>,greater<>> m_heapBig;
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{	
	vector<vector<int>> buildings;
	TEST_CLASS(UnitTest)
	{
	public:
	/*	TEST_METHOD(TestMethod00)
		{
			buildings = { {2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8} };
			auto res = Solution().getSkyline(buildings);
			AssertV2(vector<vector<int>>{ {2, 10}, { 3,15 }, { 7,12 }, { 12,0 }, { 15,10 }, { 20,8 }, { 24,0 }}, res);
		}*/
		TEST_METHOD(TestMethod01)
		{
			MedianFinder mf;
			mf.addNum(-1);
			mf.addNum(-2);
			mf.addNum(-3);
			mf.addNum(-4);
			mf.addNum(-5);
			auto t = mf.findMedian();
			AssertEx(-3.0, t);
		}
		
	};
}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛