'''
statistics:

took 4 days to finish this code.
had issue with debugging and initially made mistake.


Runnig time.

Building the Trie: O(N * K * log N)

Look up time: O (K * log N), practically less than O(N)
'''

import math

class Rank:
  def __init__(self, word, rank):
    self.word = word
    self.rank = rank

class Node:
  def __init__(self, key):
    self.key = key
    self.edges = {}
    self.children = MaxHeap(3)

class MaxHeap:
  def __init__(self, capacity):
    self.capacity = capacity
    self.list = [None]

  def add(self, node):
    self.list.append(node)
    self.bubbleUp(len(self.list) - 1)
    if len(self.list) > self.capacity + 1:
      #remove the last element.
      self.list.pop()

  def extract(self):
    if len(self.list) <= 1:
      return None

    value = self.list[1]
    self.swap(1, len(self.list) -1)
    self.list.pop()
    self.bubbleDown(1)
    return value

  def swap(self, l, r):
      tmp = self.list[l]
      self.list[l] = self.list[r]
      self.list[r] = tmp

  def left(self, p):
    return p *2

  def right(self, p):
    return p * 2 + 1

  def parent(self, c):
    return int(math.floor(c / 2))

  def is_child(self, parent, child):
    return self.list[parent].rank <= self.list[child].rank

  def bubbleUp(self, child):
    if child <= 1:
      return

    parent = self.parent(child)

    if (self.is_child(parent, child) != True):
      self.swap(parent, child)
      self.bubbleUp(parent)

  def bubbleDown(self, parent):
    if parent >= len(self.list) - 1:
      return

    left = self.left(parent)
    right = self.right(parent)

    if left >= len(self.list):
      return

    to_swap = left if right >= len(self.list) or self.is_child(left, right) == True else right
    if self.is_child(parent, to_swap) != True:
      self.swap(parent, to_swap)
      self.bubbleDown(to_swap)

class Trie:
  def __init__(self):
    self.root = Node('*')

  def add(self, word, rank):
    new_word = Rank(word, rank)
    current = self.root

    for i in new_word.word:
      next = current.edges[i] if i in current.edges else None
      if next == None:
        next = Node(i)
        current.edges[i] = next

      #add new word to next node
      next.children.add(new_word)
      current = next

  def find(self, keyword):
    found = []
    current = self.root
    for i in keyword:
      if i not in current.edges:
        return []
      current = current.edges[i]

    #collect three items from children
    for i in range(3):
      n = current.children.extract()
      if n == None:
        break
      found.append(n)

    # small cost to add back items
    for n in found:
      current.children.add(n)

    return [[i.word, i.rank] for i in found]

t = Trie()
input = [("test", 13), ("tax", 7), ("tom", 50), ("text", 100), ("top", 79),("tub", 101), ("tap", 3)]

for i in input:
  t.add(i[0], i[1])

'2(ABC) 3(DEF) 4(GHI) 5(JKL) 6(MNO) 7(PRQS) 8(TUV) 9(WXYZ)'

print("input = {}".format(input))

key = 't'
print ("key = {}  found = {}".format(key,t.find(key)))


key = 'ta'
print ("key = {} found = {}".format(key, t.find(key)))

key = 'te'
print ("key = {} found = {}".format(key, t.find(key)))


key = 'to'
print ("key = {} found = {}".format(key,  t.find(key)))

key = 'a'
print ("key = {}  found = {}".format(key, t.find(key)))