fork download
copy 
  1. #!/usr/bin/env python
  2. # coding: utf-8
  3.  
  4. # In[1]:
  5.  
  6.  
  7. class BinaryNode:
  8.     def _init_(self, key, value, left=None, right=None):
  9.         self.key = key
  10.         self.value = value
  11.         self.left = left
  12.         self.right = right
  13.  
  14.  
  15. class LinkedHeap:
  16.     def _init_(self):
  17.         self.root = None
  18.         self.size = 0
  19.  
  20.     def insert(self, key, value):
  21.         new_node = BinaryNode(key, value)
  22.         if self.root is None:
  23.             self.root = new_node
  24.             self.size += 1
  25.             return
  26.  
  27.         queue = [self.root]
  28.         while queue:
  29.             node = queue.pop(0)
  30.             if not node.left:
  31.                 node.left = new_node
  32.                 self.size += 1
  33.                 break
  34.             elif not node.right:
  35.                 node.right = new_node
  36.                 self.size += 1
  37.                 break
  38.             else:
  39.                 queue.append(node.left)
  40.                 queue.append(node.right)
  41.  
  42.         current = new_node
  43.         while current != self.root and current.key < current.parent.key:
  44.             current.key, current.parent.key = current.parent.key, current.key
  45.             current.value, current.parent.value = current.parent.value, current.value
  46.             current = current.parent
  47.  
  48.     def delete(self):
  49.         if self.root is None:
  50.             return None
  51.  
  52.         queue = [self.root]
  53.         while queue:
  54.             node = queue.pop(0)
  55.             if node.left:
  56.                 queue.append(node.left)
  57.             if node.right:
  58.                 queue.append(node.right)
  59.  
  60.         self.root.key, node.key = node.key, self.root.key
  61.         self.root.value, node.value = node.value, self.root.value
  62.  
  63.         if node.parent.right == node:
  64.             node.parent.right = None
  65.         else:
  66.             node.parent.left = None
  67.         self.size -= 1
  68.  
  69.         current = self.root
  70.         while True:
  71.             if current.left and current.left.key < current.key:
  72.                 if current.right and current.right.key < current.left.key:
  73.                     current.right.key, current.key = current.key, current.right.key
  74.                     current.right.value, current.value = current.value, current.right.value
  75.                     current = current.right
  76.                 else:
  77.                     current.left.key, current.key = current.key, current.left.key
  78.                     current.left.value, current.value = current.value, current.left.value
  79.                     current = current.left
  80.             elif current.right and current.right.key < current.key:
  81.                 current.right.key, current.key = current.key, current.right.key
  82.                 current.right.value, current.value = current.value, current.right.value
  83.                 current = current.right
  84.             else:
  85.                 break
  86.         return (node.key, node.value)
  87.  
  88.     def peek(self):
  89.         if self.root is None:
  90.             return None
  91.  
  92.         current = self.root
  93.         while current.left:
  94.             current = current.left
  95.         return (current.key, current.value)
  96.  
  97.  
  98. # In[2]:
  99.  
  100.  
  101.  
  102.  
  103.  
  104. # In[ ]:
  105.  
  106.  
  107.  
  108.  
  109.  
Success #stdin #stdout 0.03s 9632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5xDcTo
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!