supply a matching data structure that supports MakeEmpty, Insert and DeleteFreq
"""


This file is both Markdown and Python.

We keep the keys in two data structures. One is a
doubly-linked list, like this:

| &lt;- [] &lt;-&gt; [] &lt;-&gt; [] &lt;-&gt; [] -&gt; |


Here, [] is a node and | is None. Pointers are one-way
(-&gt;) or two-way (&lt;-&gt;).

Instead of being terminated by null pointers, the list
will be terminated by nodes that point to themselves. An
empty list looks like this:

[o] &lt;-&gt; [o]


Here [o] is a node that points to itself. These nodes
are called "sentinals".

Nodes keep two other pieces of data. The first is a set of
keys. The second is a frequency, which represents the
number of times each of those keys is in the multiset. For
instance, If you insert a twice and b seven times and
c seven times, there is a node in the list with
frequency set to 7 and the set of keys {b, c}.

[o] &lt;-&gt; [7, {b,c}] &lt;-&gt; [3, {a}] &lt;-&gt; [o]


The other invariants that are maintained:


The nodes are stored in frequency order
The sentinal at the high-frequency end has frequency
None
The sentinal at the low-frequency end has frequency 0
No node has negative frequency
No two nodes have the same frequency
The sentinals have empty key sets, but no other nodes
have empty key sets


So:

"""
class FreqBucket(object):
  def __init__(self, lo, hi, freq):
    self.lo = lo
    self.hi = hi
    self.freq = freq
    self.kids = set()

  def __repr__(self):
    return ("FreqBucket({}, {}, {}, {})"
            .format(self.lo.freq, self.hi.freq,
                    self.freq, self.kids))

  def unlink(self, key):
    """Remove key and remove self from the list if necessary"""
    if key in self.kids: self.kids.remove(key)
    if not self.kids:
      self.hi.lo = self.lo
      self.lo.hi = self.hi

  def increase(self, key):
    """Increase the frequency of the given key from this node"""
    result = self.hi
    if self.hi.freq != self.freq + 1:
      # There is no FreqBucket with the right .freq, so we
      # must make a new one:
      old_hi = self.hi
      self.hi = FreqBucket(self, self.hi, self.freq + 1)
      old_hi.lo = self.hi
      result = self.hi
    # Move the key to the next FreqBucket:
    result.kids.add(key)
    self.unlink(key)
    return result
"""


TallPoppies uses the list of FreqBuckets described
above. It keeps a map in which each key in the structure
maps to its corresponding FreqBucket.

"""
class TallPoppies(object):
  def __init__(self):
    # The keys of the self.keys dictionary are the inserted
    # objects; the values are FreqBuckets.
    self.keys = {}
    # Make the sentinels and link them to each other and
    # themselves. We need mini for inserts and maxi for
    # deletes.
    self.mini = FreqBucket(None, None, 0)
    self.mini.lo = self.mini
    self.maxi = FreqBucket(None, None, None)
    self.maxi.lo = self.mini
    self.maxi.hi = self.maxi
    self.mini.hi = self.maxi

  def __repr__(self):
    return ("TallPoppies({}, {}, {})"
            .format(self.keys, self.mini, self.maxi))

  def insert(self, key):
    if key in self.keys:
      self.keys[key] = self.keys[key].increase(key)
    else:
      self.keys[key] = self.mini.increase(key)

  def delete_freq(self):
    result = self.maxi.lo.kids.pop()
    self.maxi.lo.unlink(result)
    del self.keys[result]
    return result


insert and delete_freq take expected amortized O(1) time. You need hash tables and linked lists, but not search trees.