SHARE
TWEET

Untitled

a guest Oct 21st, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Min_Heap:
  2.     # Constructor
  3.     def __init__(self):
  4.         self.heap = []
  5.        
  6.        
  7.     # Return i's parent's index
  8.     def _parent_index(self, i):
  9.         return (i-1)//2
  10.    
  11.    
  12.     # Return i's left child's index
  13.     def _left_index(self, i):
  14.         return 2*i + 1
  15.    
  16.    
  17.     # Return i's right child's index
  18.     def _right_index(self, i):
  19.         return 2*i + 2
  20.    
  21.    
  22.     # Swap two given nodes
  23.     def _swap(self, a_index, b_index):
  24.         temp = self.heap[a_index]
  25.         self.heap[a_index] = self.heap[b_index]
  26.         self.heap[b_index] = temp
  27.    
  28.    
  29.     # Get minimum node
  30.     def get_min(self):
  31.         return self.heap[0]
  32.    
  33.    
  34.     # Insert a node by appending it to end and then swapping with parents till appropriate
  35.     def insert(self, node):
  36.         # Append node to end
  37.         self.heap.append(node)
  38.        
  39.         # Loop only till root node
  40.         i = len(self.heap) - 1
  41.         while i > 0:
  42.             # Get parent
  43.             parent_index = self._parent_index(i)
  44.            
  45.             # Swap if necessary, else we're done so return
  46.             if self.heap[parent_index] > node: self._swap(i, parent_index)
  47.             else: return
  48.            
  49.            
  50.             # Move pointer to parent
  51.             i = parent_index
  52.            
  53.            
  54.     # Extract the min node
  55.     def extract_min(self):
  56.         # Overwrite min node with last node and delete the last node
  57.         self.heap[0] = self.heap[-1]
  58.         del self.heap[-1]
  59.        
  60.         # Swap with smaller child till a left child doesn't exist (i.e. we've reached the end of complete binary tree)
  61.         i = 0
  62.         while self._left_index(i) < len(self.heap):
  63.             # Get children
  64.             left_index = self._left_index(i)
  65.             right_index = self._right_index(i)
  66.            
  67.             # Return if we've already reached appropriate place
  68.             if self.heap[i] <= self.heap[left_index] and self.heap[i] <= self.heap[right_index]:
  69.                 return
  70.             else:
  71.                 # Swap with appropriate child
  72.                 if self.heap[left_index] < self.heap[right_index]:
  73.                     self._swap(i, left_index)
  74.                     i = left_index
  75.                 else:
  76.                     self._swap(i, right_index)
  77.                     i = right_index
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top