对顶堆——中位数神器

对顶堆——中位数神器

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

对顶堆——中位数神器

平衡值

如果固定序列的大小为 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;
    }
};
上一篇:BP信用数据配置更新


下一篇:5.7 阅读材料