• API
• FAQ
• Tools
• Archive
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.
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!

Top