对顶堆——中位数神器

对顶堆，即一个大根堆和一个小根堆组合而成的一个数据结构，可以很方便的维护可变区间中位数。

平衡值

如果固定序列的大小为 n n n，那么平衡值指堆的最大大小。如果 n n n为偶数，大根堆的平衡值 l e f t N u m leftNum leftNum等于小根堆的平衡值 r i g h t N u m rightNum rightNum等于 n 2 \frac{n}{2} 2n​。如果 n n n为奇数，则 l e f t N u m = n / 2 leftNum = n/2 leftNum=n/2（整除）， r i g h t N u m = n − l e f t N u m rightNum = n - leftNum rightNum=n−leftNum。（不一定这么算，也可以让rightNum大一）

入堆

1. 检查左侧大根堆是否满足平衡要求，如果不满足平衡（ b q . s i z e ( ) < l e f t N u m bq.size() \lt leftNum bq.size()<leftNum）要求则直接插入大根堆。
2. 如果满足平衡要求，将当前元素和大根堆对顶元素比较，如果比对顶元素大或等于，则应该放在小根堆里面；如果比对顶元素小，则说明应该放进小根堆里面，并且对顶元素应该出堆，放进小根堆里面。

出堆

因为C++的std::priority_queue不支持删除元素，所以我们只能标记这个元素处于删除状态，并判这个元素属于哪一个堆，将该堆的平衡值加一，例如在大根堆里面则 l e f t N u m + 1 leftNum+1 leftNum+1。

这之后，如果有元素入堆，则应该先检查对顶元素是否为删除元素，如果是，直接将这个元素出堆，并调整平衡值，再按照平衡值调整正确的堆大小即可。

取中位数

如果 n n n为偶数，那么中位数就是大根堆堆顶元素加上小根堆堆顶元素的一半；如果是奇数，则应该按照平衡值去取。

例题

LeetCode 480 滑动窗口的中位数

class Solution
{
public:
    vector<double> medianSlidingWindow(vector<int> &nums, int k)
    {
        vector<double> ans;
        if (k == 1)
        {
            for (int i : nums)
            {
                ans.push_back(i);
            }
            return ans;
        }

        priority_queue<int> bp;
        priority_queue<int, vector<int>, greater<int>> sp;

        unordered_map<int, int> mp;

        int leftNum = k / 2;
        int rightNum = k - leftNum;

        for (int i = 0; i < k; i++)
        {
            if (bp.size() < leftNum)
                bp.push(nums[i]);
            else
            {
                if (bp.top() > nums[i])
                {
                    sp.push(bp.top());
                    bp.pop();
                    bp.push(nums[i]);
                }
                else
                {
                    sp.push(nums[i]);
                }
            }
        }

        if (k % 2 == 0)
        {
            ans.push_back((((double)bp.top()) + sp.top()) / 2);
        }
        else
        {
            ans.push_back(sp.top());
        }

        for (int i = 1, j = k; j < nums.size(); i++, j++)
        {
            mp[nums[i - 1]]++;

            if (nums[i - 1] <= bp.top())
            {
                leftNum++;
            }
            else
            {
                rightNum++;
            }

            while (!bp.empty() && mp.count(bp.top()))
            {
                mp[bp.top()]--;
                if (mp[bp.top()] == 0)
                {
                    mp.erase(bp.top());
                }
                bp.pop();
                leftNum--;
            }

            while (!sp.empty() && mp.count(sp.top()))
            {
                mp[sp.top()]--;
                if (mp[sp.top()] == 0)
                {
                    mp.erase(sp.top());
                }
                sp.pop();
                rightNum--;
            }

            while (bp.size() < leftNum && !sp.empty())
            {
                if (mp.count(sp.top()))
                {
                    mp[sp.top()]--;
                    if (mp[sp.top()] == 0)
                    {
                        mp.erase(sp.top());
                    }
                    sp.pop();
                    rightNum--;
                }
                else
                {
                    bp.push(sp.top());
                    sp.pop();
                }
            }

            while (!sp.empty() && mp.count(sp.top()))
            {
                mp[sp.top()]--;
                if (mp[sp.top()] == 0)
                {
                    mp.erase(sp.top());
                }
                sp.pop();
                rightNum--;
            }

            if (bp.size() < leftNum)
                bp.push(nums[j]);
            else
            {
                if (bp.top() > nums[j])
                {
                    sp.push(bp.top());
                    bp.pop();
                    bp.push(nums[j]);
                }
                else
                {
                    sp.push(nums[j]);
                }
            }

            while (!bp.empty() && mp.count(bp.top()))
            {
                mp[bp.top()]--;
                if (mp[bp.top()] == 0)
                {
                    mp.erase(bp.top());
                }
                bp.pop();
                leftNum--;
            }
            if (k % 2 == 0)
            {
                ans.push_back((((double)bp.top()) / 2 + ((double)sp.top()) / 2));
            }
            else
            {
                ans.push_back(sp.top());
            }
        }
        return ans;
    }
};