#!/usr/bin/env python
# coding: utf-8
# In[1]:
class BinaryNode:
def _init_(self, key, value, left=None, right=None):
self.key = key
self.value = value
self.left = left
self.right = right
class LinkedHeap:
def _init_(self):
self.root = None
self.size = 0
def insert(self, key, value):
new_node = BinaryNode(key, value)
if self.root is None:
self.root = new_node
self.size += 1
return
queue = [self.root]
while queue:
node = queue.pop(0)
if not node.left:
node.left = new_node
self.size += 1
break
elif not node.right:
node.right = new_node
self.size += 1
break
else:
queue.append(node.left)
queue.append(node.right)
current = new_node
while current != self.root and current.key < current.parent.key:
current.key, current.parent.key = current.parent.key, current.key
current.value, current.parent.value = current.parent.value, current.value
current = current.parent
def delete(self):
if self.root is None:
return None
queue = [self.root]
while queue:
node = queue.pop(0)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
self.root.key, node.key = node.key, self.root.key
self.root.value, node.value = node.value, self.root.value
if node.parent.right == node:
node.parent.right = None
else:
node.parent.left = None
self.size -= 1
current = self.root
while True:
if current.left and current.left.key < current.key:
if current.right and current.right.key < current.left.key:
current.right.key, current.key = current.key, current.right.key
current.right.value, current.value = current.value, current.right.value
current = current.right
else:
current.left.key, current.key = current.key, current.left.key
current.left.value, current.value = current.value, current.left.value
current = current.left
elif current.right and current.right.key < current.key:
current.right.key, current.key = current.key, current.right.key
current.right.value, current.value = current.value, current.right.value
current = current.right
else:
break
return (node.key, node.value)
def peek(self):
if self.root is None:
return None
current = self.root
while current.left:
current = current.left
return (current.key, current.value)
# In[2]:
# In[ ]:
IyEvdXNyL2Jpbi9lbnYgcHl0aG9uCiMgY29kaW5nOiB1dGYtOAoKIyBJblsxXToKCgpjbGFzcyBCaW5hcnlOb2RlOgogICAgZGVmIF9pbml0XyhzZWxmLCBrZXksIHZhbHVlLCBsZWZ0PU5vbmUsIHJpZ2h0PU5vbmUpOgogICAgICAgIHNlbGYua2V5ID0ga2V5CiAgICAgICAgc2VsZi52YWx1ZSA9IHZhbHVlCiAgICAgICAgc2VsZi5sZWZ0ID0gbGVmdAogICAgICAgIHNlbGYucmlnaHQgPSByaWdodAoKCmNsYXNzIExpbmtlZEhlYXA6CiAgICBkZWYgX2luaXRfKHNlbGYpOgogICAgICAgIHNlbGYucm9vdCA9IE5vbmUKICAgICAgICBzZWxmLnNpemUgPSAwCgogICAgZGVmIGluc2VydChzZWxmLCBrZXksIHZhbHVlKToKICAgICAgICBuZXdfbm9kZSA9IEJpbmFyeU5vZGUoa2V5LCB2YWx1ZSkKICAgICAgICBpZiBzZWxmLnJvb3QgaXMgTm9uZToKICAgICAgICAgICAgc2VsZi5yb290ID0gbmV3X25vZGUKICAgICAgICAgICAgc2VsZi5zaXplICs9IDEKICAgICAgICAgICAgcmV0dXJuCiAgICAKICAgICAgICBxdWV1ZSA9IFtzZWxmLnJvb3RdCiAgICAgICAgd2hpbGUgcXVldWU6CiAgICAgICAgICAgIG5vZGUgPSBxdWV1ZS5wb3AoMCkKICAgICAgICAgICAgaWYgbm90IG5vZGUubGVmdDoKICAgICAgICAgICAgICAgIG5vZGUubGVmdCA9IG5ld19ub2RlCiAgICAgICAgICAgICAgICBzZWxmLnNpemUgKz0gMQogICAgICAgICAgICAgICAgYnJlYWsKICAgICAgICAgICAgZWxpZiBub3Qgbm9kZS5yaWdodDoKICAgICAgICAgICAgICAgIG5vZGUucmlnaHQgPSBuZXdfbm9kZQogICAgICAgICAgICAgICAgc2VsZi5zaXplICs9IDEKICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICBxdWV1ZS5hcHBlbmQobm9kZS5sZWZ0KQogICAgICAgICAgICAgICAgcXVldWUuYXBwZW5kKG5vZGUucmlnaHQpCiAgICAgICAKICAgICAgICBjdXJyZW50ID0gbmV3X25vZGUKICAgICAgICB3aGlsZSBjdXJyZW50ICE9IHNlbGYucm9vdCBhbmQgY3VycmVudC5rZXkgPCBjdXJyZW50LnBhcmVudC5rZXk6CiAgICAgICAgICAgIGN1cnJlbnQua2V5LCBjdXJyZW50LnBhcmVudC5rZXkgPSBjdXJyZW50LnBhcmVudC5rZXksIGN1cnJlbnQua2V5CiAgICAgICAgICAgIGN1cnJlbnQudmFsdWUsIGN1cnJlbnQucGFyZW50LnZhbHVlID0gY3VycmVudC5wYXJlbnQudmFsdWUsIGN1cnJlbnQudmFsdWUKICAgICAgICAgICAgY3VycmVudCA9IGN1cnJlbnQucGFyZW50CgogICAgZGVmIGRlbGV0ZShzZWxmKToKICAgICAgICBpZiBzZWxmLnJvb3QgaXMgTm9uZToKICAgICAgICAgICAgcmV0dXJuIE5vbmUKICAgICAKICAgICAgICBxdWV1ZSA9IFtzZWxmLnJvb3RdCiAgICAgICAgd2hpbGUgcXVldWU6CiAgICAgICAgICAgIG5vZGUgPSBxdWV1ZS5wb3AoMCkKICAgICAgICAgICAgaWYgbm9kZS5sZWZ0OgogICAgICAgICAgICAgICAgcXVldWUuYXBwZW5kKG5vZGUubGVmdCkKICAgICAgICAgICAgaWYgbm9kZS5yaWdodDoKICAgICAgICAgICAgICAgIHF1ZXVlLmFwcGVuZChub2RlLnJpZ2h0KQogICAKICAgICAgICBzZWxmLnJvb3Qua2V5LCBub2RlLmtleSA9IG5vZGUua2V5LCBzZWxmLnJvb3Qua2V5CiAgICAgICAgc2VsZi5yb290LnZhbHVlLCBub2RlLnZhbHVlID0gbm9kZS52YWx1ZSwgc2VsZi5yb290LnZhbHVlCiAgICAgICAKICAgICAgICBpZiBub2RlLnBhcmVudC5yaWdodCA9PSBub2RlOgogICAgICAgICAgICBub2RlLnBhcmVudC5yaWdodCA9IE5vbmUKICAgICAgICBlbHNlOgogICAgICAgICAgICBub2RlLnBhcmVudC5sZWZ0ID0gTm9uZQogICAgICAgIHNlbGYuc2l6ZSAtPSAxCiAgICAgCiAgICAgICAgY3VycmVudCA9IHNlbGYucm9vdAogICAgICAgIHdoaWxlIFRydWU6CiAgICAgICAgICAgIGlmIGN1cnJlbnQubGVmdCBhbmQgY3VycmVudC5sZWZ0LmtleSA8IGN1cnJlbnQua2V5OgogICAgICAgICAgICAgICAgaWYgY3VycmVudC5yaWdodCBhbmQgY3VycmVudC5yaWdodC5rZXkgPCBjdXJyZW50LmxlZnQua2V5OgogICAgICAgICAgICAgICAgICAgIGN1cnJlbnQucmlnaHQua2V5LCBjdXJyZW50LmtleSA9IGN1cnJlbnQua2V5LCBjdXJyZW50LnJpZ2h0LmtleQogICAgICAgICAgICAgICAgICAgIGN1cnJlbnQucmlnaHQudmFsdWUsIGN1cnJlbnQudmFsdWUgPSBjdXJyZW50LnZhbHVlLCBjdXJyZW50LnJpZ2h0LnZhbHVlCiAgICAgICAgICAgICAgICAgICAgY3VycmVudCA9IGN1cnJlbnQucmlnaHQKICAgICAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICAgICAgY3VycmVudC5sZWZ0LmtleSwgY3VycmVudC5rZXkgPSBjdXJyZW50LmtleSwgY3VycmVudC5sZWZ0LmtleQogICAgICAgICAgICAgICAgICAgIGN1cnJlbnQubGVmdC52YWx1ZSwgY3VycmVudC52YWx1ZSA9IGN1cnJlbnQudmFsdWUsIGN1cnJlbnQubGVmdC52YWx1ZQogICAgICAgICAgICAgICAgICAgIGN1cnJlbnQgPSBjdXJyZW50LmxlZnQKICAgICAgICAgICAgZWxpZiBjdXJyZW50LnJpZ2h0IGFuZCBjdXJyZW50LnJpZ2h0LmtleSA8IGN1cnJlbnQua2V5OgogICAgICAgICAgICAgICAgY3VycmVudC5yaWdodC5rZXksIGN1cnJlbnQua2V5ID0gY3VycmVudC5rZXksIGN1cnJlbnQucmlnaHQua2V5CiAgICAgICAgICAgICAgICBjdXJyZW50LnJpZ2h0LnZhbHVlLCBjdXJyZW50LnZhbHVlID0gY3VycmVudC52YWx1ZSwgY3VycmVudC5yaWdodC52YWx1ZQogICAgICAgICAgICAgICAgY3VycmVudCA9IGN1cnJlbnQucmlnaHQKICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIGJyZWFrCiAgICAgICAgcmV0dXJuIChub2RlLmtleSwgbm9kZS52YWx1ZSkKCiAgICBkZWYgcGVlayhzZWxmKToKICAgICAgICBpZiBzZWxmLnJvb3QgaXMgTm9uZToKICAgICAgICAgICAgcmV0dXJuIE5vbmUKICAgICAgICAKICAgICAgICBjdXJyZW50ID0gc2VsZi5yb290CiAgICAgICAgd2hpbGUgY3VycmVudC5sZWZ0OgogICAgICAgICAgICBjdXJyZW50ID0gY3VycmVudC5sZWZ0CiAgICAgICAgcmV0dXJuIChjdXJyZW50LmtleSwgY3VycmVudC52YWx1ZSkKCgojIEluWzJdOgoKCgoKCiMgSW5bIF06CgoKCgo=