#!/usr/bin/env python
# -*- coding: utf-8 -*-
# File  : DualHeap.py
# Author: hugh
# Date  : 2021/2/3

import collections
from typing import List
import heapq


class DualHeap:

    def __init__(self, k: int):
        """
        初始化内容
        :param k:
        """
        # 大根堆 维护较小的一半元素，注意python没有大根堆，需要所有元素取反
        self.small = list()
        # 小根堆 维护较大的元素
        self.large = list()
        # 哈希表 记录 延迟删除的元素， key为元素，value为需要删除的次数
        self.delayed = collections.Counter()

        self.k = k
        # small 和 large 包含的元素个数，需扣除延迟删除的个数
        self.small_size = 0
        self.large_size = 0

    def prune(self, heap: List[int]):
        """
        不断弹出heap的堆顶元素，并且更新哈希表
        :param heap:
        :return:
        """
        while heap:
            num = heap[0]
            if heap is self.small:
                num = -num

            if num in self.delayed:
                self.delayed[num] -= 1
                if self.delayed[num] == 0:
                    self.delayed.pop(num)
                heapq.heappop(heap)
            else:
                break

    def make_balance(self):
        """
        调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
        :return:
        """
        if self.small_size > self.large_size + 1:
            heapq.heappush(self.large, -self.small[0])
            heapq.heappop(self.small)
            self.small_size -= 1
            self.large_size += 1
            # small 堆顶元素被移除，需要进行 prune
            self.prune(self.small)
        elif self.small_size < self.large_size:
            heapq.heappush(self.small, -self.large[0])
            heapq.heappop(self.large)
            self.small_size += 1
            self.large_size -= 1
            self.prune(self.large)

    def insert(self, num: int):
        """

        :param num:
        :return:
        """
        if not self.small or num <= -self.small[0]:
            heapq.heappush(self.small, -num)
            self.small_size += 1
        else:
            heapq.heappush(self.large, num)
            self.large_size += 1
        self.makeBalance()

    def erase(self, num: int):
        """

        :param num:
        :return:
        """
        self.delayed[num] += 1
        if num <= -self.small[0]:
            self.small_size -= 1
            if num == -self.small[0]:
                self.prune(self.small)
        else:
            self.large_size -= 1
            if num == self.small[0]:
                self.prune(self.large)
        self.makeBalance()

    def get_median(self) -> float:
        """

        :return:
        """
        return float(-self.small[0]) if self.k % 2 == 0 else (-self.small[0] + self.large[0]) / 2