dsa.heap
Module containing heap (max heap), min heap and priority queue classes.
1""" Module containing heap (max heap), min heap and priority queue classes. """ 2class Heap: 3 """ 4 A max heap implementation. 5 """ 6 def __init__(self): 7 self._array = [] 8 9 @classmethod 10 def from_list(cls, mylist: list): 11 """ 12 Create a heap from a list of elements. 13 Args: 14 mylist (list): The list of elements to be inserted into the heap. 15 Returns: 16 Heap: An instance of the heap with all elements from the list inserted. 17 """ 18 19 hp = cls() 20 for e in mylist: 21 hp.insert(e) 22 23 return hp 24 25 def raw_view(self) -> list: 26 """ 27 Return the heap in its array representation. 28 29 Returns: 30 list: The list representation of the heap. 31 """ 32 33 return self._array 34 35 def root(self): 36 """ 37 Get the root value. 38 39 Returns: 40 The root node's value. None if count is 0. 41 """ 42 if self.count() == 0: 43 return None 44 45 return self._array[0] 46 47 def peek(self): 48 """ 49 Get the max value of the max heap. 50 51 Returns: 52 The maximum value of the max heap. 53 """ 54 return self.root() 55 56 def last(self): 57 """ 58 Get the last node of the max heap. 59 60 Returns: 61 The last node's value. 62 None if count is 0. 63 """ 64 if self.count() == 0: 65 return None 66 67 return self._array[-1] 68 69 def left_index(self, index: int) -> int: 70 """ 71 Get the index of the left child. 72 73 Args: 74 index (int): The index of the node. 75 76 Returns: 77 Return the index of the left child. 78 """ 79 return (index * 2) + 1 80 81 def right_index(self, index: int) -> int: 82 """ 83 Get the index of the right child. 84 85 Args: 86 index (int): The index of the node. 87 88 Returns: 89 Return the index of the right child. 90 """ 91 return (index * 2) + 2 92 93 def parent_index(self, index: int) -> int: 94 """ 95 Get the index of the parent node. 96 97 Args: 98 index (int): The index of the node. 99 100 Returns: 101 Return the index of the parent child. 102 """ 103 return (index - 1) // 2 104 105 def has_left(self, index: int) -> bool: 106 """ 107 Check if current node has an left child. 108 109 Args: 110 index (int): The index of the node. 111 112 Returns: 113 Boolean on whether a node has a left child node. 114 """ 115 return self.left_index(index) < self.count() 116 117 def has_right(self, index: int) -> bool: 118 """ 119 Check if current node has an right child. 120 121 Args: 122 index (int): The index of the node. 123 124 Returns: 125 Boolean on whether a node has a right child node. 126 """ 127 return self.right_index(index) < self.count() 128 129 def has_parent(self, index: int) -> bool: 130 """ 131 Check if a node has a parent node. 132 133 Args: 134 index (int): The index of the node. 135 136 Returns: 137 Boolean on whether a node has a parent node. 138 """ 139 return self.parent_index(index) >= 0 140 141 def insert(self, value): 142 """ 143 Insert a value into the heap. 144 145 Args: 146 value: The value to insert. 147 """ 148 self._array.append(value) 149 150 start_index = self.count() - 1 151 self.heapify_up(start_index) 152 153 def heapify_up(self, index: int): 154 """ 155 Perform heapify up starting at a given index. 156 157 Args: 158 index (int): The starting index. 159 """ 160 parent_index = self.parent_index(index) 161 while self.has_parent(index) and self._array[index] > self._array[parent_index]: 162 self._array[index], self._array[parent_index] = self._array[parent_index], self._array[index] 163 index = parent_index 164 parent_index = self.parent_index(index) 165 166 def pop(self): 167 """ 168 Return the value of the root node (max value) and remove it from the heap. 169 170 Returns: 171 Return the value from the root node. 172 """ 173 root_value = self.root() 174 175 # start at root node 176 start_index = 0 177 if self.count() == 0: 178 raise Exception("Heap is empty") 179 if self.count() == 1: 180 self._array.pop() 181 else: 182 self._array[start_index] = self._array.pop() 183 184 self.heapify_down(start_index) 185 return root_value 186 187 def heapify_down(self, index: int): 188 """ 189 Perform heapify down starting at a given index. 190 191 Args: 192 index (int): The starting index. 193 """ 194 while self.has_left(index): 195 higher_index = self.left_index(index) 196 right_index = self.right_index(index) 197 if self.has_right(index) and self._array[right_index] > self._array[higher_index]: 198 higher_index = right_index 199 200 if self._array[index] > self._array[higher_index]: 201 break 202 else: 203 self._array[index], self._array[higher_index] = self._array[higher_index], self._array[index] 204 205 index = higher_index 206 207 def enumerate(self): 208 """ 209 Return the enumeration of a heap. 210 211 Returns: 212 Enumeration of a heap. 213 """ 214 return enumerate(self._array) 215 216 def count(self) -> int: 217 """ 218 Return the number of items in the heap. 219 220 Returns: 221 The number of items in the heap. 222 """ 223 return len(self._array) 224 225 def is_empty(self) -> bool: 226 """ 227 Check if a heap has any items. 228 229 Returns: 230 True if heap has no items. 231 False if heap has more than 0 items. 232 """ 233 return self.count() == 0 234 235 def print(self): 236 """ 237 Print the contents of a heap. 238 """ 239 node_count = 1 240 for i in range(self.count()): 241 if i + 1 >= node_count: 242 print() 243 node_count *= 2 244 print(self._array[i], end=" ") 245 246 def to_sorted_list(self) -> list: 247 """ 248 Return a sorted list from the heap. 249 250 Returns: 251 A sorted list. 252 """ 253 temp_heap = Heap() 254 temp_heap._array = self._array[:] 255 256 result = [] 257 while not temp_heap.is_empty(): 258 result.append(temp_heap.pop()) 259 260 return result 261 262 def __repr__(self): 263 """ 264 Return string representation of a heap in order of priority. 265 """ 266 ordered_list = self.to_sorted_list() 267 return "[" + " ".join([str(e) for e in ordered_list]) + "]" 268 269 def __len__(self): 270 """ 271 Get the number of items in the priority queue. 272 273 Returns: 274 Number of items in the priority queue 275 """ 276 return self.count() 277 278class MinHeap(Heap): 279 def heapify_up(self, index: int): 280 """ 281 Perform heapify up starting at a given index. 282 283 Args: 284 index (int): The starting index. 285 """ 286 parent_index = self.parent_index(index) 287 while self.has_parent(index) and self._array[index] < self._array[parent_index]: 288 self._array[index], self._array[parent_index] = self._array[parent_index], self._array[index] 289 index = parent_index 290 parent_index = self.parent_index(index) 291 292 def heapify_down(self, index: int): 293 """ 294 Perform heapify down starting at a given index. 295 296 Args: 297 index (int): The starting index. 298 """ 299 while self.has_left(index): 300 higher_index = self.left_index(index) 301 right_index = self.right_index(index) 302 if self.has_right(index) and self._array[right_index] < self._array[higher_index]: 303 higher_index = right_index 304 305 if self._array[index] < self._array[higher_index]: 306 break 307 else: 308 self._array[index], self._array[higher_index] = self._array[higher_index], self._array[index] 309 310 index = higher_index 311 312 313class PriorityQueue(MinHeap): 314 """ 315 A priority queue implementation in Python. 316 """ 317 def push(self, priority: int, item): 318 """ 319 Insert an item with a priority into the priority queue. 320 321 Args: 322 priority (int): Priority of item. 323 item: The item to insert. 324 """ 325 super().insert((priority, item)) 326 327 def pop(self): 328 """ 329 Return and remove the highest priority value in the heap. 330 331 Returns: 332 Return The highest priority value in the heap. 333 """ 334 priority, item = super().pop() 335 return item 336 337 def pop_pair(self) -> tuple: 338 """ 339 Return and remove the highest priority value pair in the heap. 340 341 Returns: 342 Return the highest priority, value pair (tuple) in the heap. 343 """ 344 return super().pop() 345 346 def peek(self): 347 """ 348 Return the highest priority value in the heap. 349 350 Returns: 351 Return The highest priority value in the heap. 352 """ 353 priority, item = super().peek() 354 return item 355 356 def peek_pair(self) -> tuple: 357 """ 358 Return the highest priority value pair in the heap. 359 360 Returns: 361 Return the highest priority, value pair (tuple) in the heap. 362 """ 363 return super().peek() 364 365 def to_string_with_priority(self): 366 """ 367 Return string representation of a heap in order of priority. 368 """ 369 temp_array = self._array[:] 370 result = [] 371 while not self.is_empty(): 372 result.append(str(self.pop_pair())) 373 self._array = temp_array 374 375 return "[" + " ".join(result) + "]"
class
Heap:
3class Heap: 4 """ 5 A max heap implementation. 6 """ 7 def __init__(self): 8 self._array = [] 9 10 @classmethod 11 def from_list(cls, mylist: list): 12 """ 13 Create a heap from a list of elements. 14 Args: 15 mylist (list): The list of elements to be inserted into the heap. 16 Returns: 17 Heap: An instance of the heap with all elements from the list inserted. 18 """ 19 20 hp = cls() 21 for e in mylist: 22 hp.insert(e) 23 24 return hp 25 26 def raw_view(self) -> list: 27 """ 28 Return the heap in its array representation. 29 30 Returns: 31 list: The list representation of the heap. 32 """ 33 34 return self._array 35 36 def root(self): 37 """ 38 Get the root value. 39 40 Returns: 41 The root node's value. None if count is 0. 42 """ 43 if self.count() == 0: 44 return None 45 46 return self._array[0] 47 48 def peek(self): 49 """ 50 Get the max value of the max heap. 51 52 Returns: 53 The maximum value of the max heap. 54 """ 55 return self.root() 56 57 def last(self): 58 """ 59 Get the last node of the max heap. 60 61 Returns: 62 The last node's value. 63 None if count is 0. 64 """ 65 if self.count() == 0: 66 return None 67 68 return self._array[-1] 69 70 def left_index(self, index: int) -> int: 71 """ 72 Get the index of the left child. 73 74 Args: 75 index (int): The index of the node. 76 77 Returns: 78 Return the index of the left child. 79 """ 80 return (index * 2) + 1 81 82 def right_index(self, index: int) -> int: 83 """ 84 Get the index of the right child. 85 86 Args: 87 index (int): The index of the node. 88 89 Returns: 90 Return the index of the right child. 91 """ 92 return (index * 2) + 2 93 94 def parent_index(self, index: int) -> int: 95 """ 96 Get the index of the parent node. 97 98 Args: 99 index (int): The index of the node. 100 101 Returns: 102 Return the index of the parent child. 103 """ 104 return (index - 1) // 2 105 106 def has_left(self, index: int) -> bool: 107 """ 108 Check if current node has an left child. 109 110 Args: 111 index (int): The index of the node. 112 113 Returns: 114 Boolean on whether a node has a left child node. 115 """ 116 return self.left_index(index) < self.count() 117 118 def has_right(self, index: int) -> bool: 119 """ 120 Check if current node has an right child. 121 122 Args: 123 index (int): The index of the node. 124 125 Returns: 126 Boolean on whether a node has a right child node. 127 """ 128 return self.right_index(index) < self.count() 129 130 def has_parent(self, index: int) -> bool: 131 """ 132 Check if a node has a parent node. 133 134 Args: 135 index (int): The index of the node. 136 137 Returns: 138 Boolean on whether a node has a parent node. 139 """ 140 return self.parent_index(index) >= 0 141 142 def insert(self, value): 143 """ 144 Insert a value into the heap. 145 146 Args: 147 value: The value to insert. 148 """ 149 self._array.append(value) 150 151 start_index = self.count() - 1 152 self.heapify_up(start_index) 153 154 def heapify_up(self, index: int): 155 """ 156 Perform heapify up starting at a given index. 157 158 Args: 159 index (int): The starting index. 160 """ 161 parent_index = self.parent_index(index) 162 while self.has_parent(index) and self._array[index] > self._array[parent_index]: 163 self._array[index], self._array[parent_index] = self._array[parent_index], self._array[index] 164 index = parent_index 165 parent_index = self.parent_index(index) 166 167 def pop(self): 168 """ 169 Return the value of the root node (max value) and remove it from the heap. 170 171 Returns: 172 Return the value from the root node. 173 """ 174 root_value = self.root() 175 176 # start at root node 177 start_index = 0 178 if self.count() == 0: 179 raise Exception("Heap is empty") 180 if self.count() == 1: 181 self._array.pop() 182 else: 183 self._array[start_index] = self._array.pop() 184 185 self.heapify_down(start_index) 186 return root_value 187 188 def heapify_down(self, index: int): 189 """ 190 Perform heapify down starting at a given index. 191 192 Args: 193 index (int): The starting index. 194 """ 195 while self.has_left(index): 196 higher_index = self.left_index(index) 197 right_index = self.right_index(index) 198 if self.has_right(index) and self._array[right_index] > self._array[higher_index]: 199 higher_index = right_index 200 201 if self._array[index] > self._array[higher_index]: 202 break 203 else: 204 self._array[index], self._array[higher_index] = self._array[higher_index], self._array[index] 205 206 index = higher_index 207 208 def enumerate(self): 209 """ 210 Return the enumeration of a heap. 211 212 Returns: 213 Enumeration of a heap. 214 """ 215 return enumerate(self._array) 216 217 def count(self) -> int: 218 """ 219 Return the number of items in the heap. 220 221 Returns: 222 The number of items in the heap. 223 """ 224 return len(self._array) 225 226 def is_empty(self) -> bool: 227 """ 228 Check if a heap has any items. 229 230 Returns: 231 True if heap has no items. 232 False if heap has more than 0 items. 233 """ 234 return self.count() == 0 235 236 def print(self): 237 """ 238 Print the contents of a heap. 239 """ 240 node_count = 1 241 for i in range(self.count()): 242 if i + 1 >= node_count: 243 print() 244 node_count *= 2 245 print(self._array[i], end=" ") 246 247 def to_sorted_list(self) -> list: 248 """ 249 Return a sorted list from the heap. 250 251 Returns: 252 A sorted list. 253 """ 254 temp_heap = Heap() 255 temp_heap._array = self._array[:] 256 257 result = [] 258 while not temp_heap.is_empty(): 259 result.append(temp_heap.pop()) 260 261 return result 262 263 def __repr__(self): 264 """ 265 Return string representation of a heap in order of priority. 266 """ 267 ordered_list = self.to_sorted_list() 268 return "[" + " ".join([str(e) for e in ordered_list]) + "]" 269 270 def __len__(self): 271 """ 272 Get the number of items in the priority queue. 273 274 Returns: 275 Number of items in the priority queue 276 """ 277 return self.count()
A max heap implementation.
@classmethod
def
from_list(cls, mylist: list):
10 @classmethod 11 def from_list(cls, mylist: list): 12 """ 13 Create a heap from a list of elements. 14 Args: 15 mylist (list): The list of elements to be inserted into the heap. 16 Returns: 17 Heap: An instance of the heap with all elements from the list inserted. 18 """ 19 20 hp = cls() 21 for e in mylist: 22 hp.insert(e) 23 24 return hp
Create a heap from a list of elements. Args: mylist (list): The list of elements to be inserted into the heap. Returns: Heap: An instance of the heap with all elements from the list inserted.
def
raw_view(self) -> list:
26 def raw_view(self) -> list: 27 """ 28 Return the heap in its array representation. 29 30 Returns: 31 list: The list representation of the heap. 32 """ 33 34 return self._array
Return the heap in its array representation.
Returns: list: The list representation of the heap.
def
root(self):
36 def root(self): 37 """ 38 Get the root value. 39 40 Returns: 41 The root node's value. None if count is 0. 42 """ 43 if self.count() == 0: 44 return None 45 46 return self._array[0]
Get the root value.
Returns: The root node's value. None if count is 0.
def
peek(self):
48 def peek(self): 49 """ 50 Get the max value of the max heap. 51 52 Returns: 53 The maximum value of the max heap. 54 """ 55 return self.root()
Get the max value of the max heap.
Returns: The maximum value of the max heap.
def
last(self):
57 def last(self): 58 """ 59 Get the last node of the max heap. 60 61 Returns: 62 The last node's value. 63 None if count is 0. 64 """ 65 if self.count() == 0: 66 return None 67 68 return self._array[-1]
Get the last node of the max heap.
Returns: The last node's value. None if count is 0.
def
left_index(self, index: int) -> int:
70 def left_index(self, index: int) -> int: 71 """ 72 Get the index of the left child. 73 74 Args: 75 index (int): The index of the node. 76 77 Returns: 78 Return the index of the left child. 79 """ 80 return (index * 2) + 1
Get the index of the left child.
Args: index (int): The index of the node.
Returns: Return the index of the left child.
def
right_index(self, index: int) -> int:
82 def right_index(self, index: int) -> int: 83 """ 84 Get the index of the right child. 85 86 Args: 87 index (int): The index of the node. 88 89 Returns: 90 Return the index of the right child. 91 """ 92 return (index * 2) + 2
Get the index of the right child.
Args: index (int): The index of the node.
Returns: Return the index of the right child.
def
parent_index(self, index: int) -> int:
94 def parent_index(self, index: int) -> int: 95 """ 96 Get the index of the parent node. 97 98 Args: 99 index (int): The index of the node. 100 101 Returns: 102 Return the index of the parent child. 103 """ 104 return (index - 1) // 2
Get the index of the parent node.
Args: index (int): The index of the node.
Returns: Return the index of the parent child.
def
has_left(self, index: int) -> bool:
106 def has_left(self, index: int) -> bool: 107 """ 108 Check if current node has an left child. 109 110 Args: 111 index (int): The index of the node. 112 113 Returns: 114 Boolean on whether a node has a left child node. 115 """ 116 return self.left_index(index) < self.count()
Check if current node has an left child.
Args: index (int): The index of the node.
Returns: Boolean on whether a node has a left child node.
def
has_right(self, index: int) -> bool:
118 def has_right(self, index: int) -> bool: 119 """ 120 Check if current node has an right child. 121 122 Args: 123 index (int): The index of the node. 124 125 Returns: 126 Boolean on whether a node has a right child node. 127 """ 128 return self.right_index(index) < self.count()
Check if current node has an right child.
Args: index (int): The index of the node.
Returns: Boolean on whether a node has a right child node.
def
has_parent(self, index: int) -> bool:
130 def has_parent(self, index: int) -> bool: 131 """ 132 Check if a node has a parent node. 133 134 Args: 135 index (int): The index of the node. 136 137 Returns: 138 Boolean on whether a node has a parent node. 139 """ 140 return self.parent_index(index) >= 0
Check if a node has a parent node.
Args: index (int): The index of the node.
Returns: Boolean on whether a node has a parent node.
def
insert(self, value):
142 def insert(self, value): 143 """ 144 Insert a value into the heap. 145 146 Args: 147 value: The value to insert. 148 """ 149 self._array.append(value) 150 151 start_index = self.count() - 1 152 self.heapify_up(start_index)
Insert a value into the heap.
Args: value: The value to insert.
def
heapify_up(self, index: int):
154 def heapify_up(self, index: int): 155 """ 156 Perform heapify up starting at a given index. 157 158 Args: 159 index (int): The starting index. 160 """ 161 parent_index = self.parent_index(index) 162 while self.has_parent(index) and self._array[index] > self._array[parent_index]: 163 self._array[index], self._array[parent_index] = self._array[parent_index], self._array[index] 164 index = parent_index 165 parent_index = self.parent_index(index)
Perform heapify up starting at a given index.
Args: index (int): The starting index.
def
pop(self):
167 def pop(self): 168 """ 169 Return the value of the root node (max value) and remove it from the heap. 170 171 Returns: 172 Return the value from the root node. 173 """ 174 root_value = self.root() 175 176 # start at root node 177 start_index = 0 178 if self.count() == 0: 179 raise Exception("Heap is empty") 180 if self.count() == 1: 181 self._array.pop() 182 else: 183 self._array[start_index] = self._array.pop() 184 185 self.heapify_down(start_index) 186 return root_value
Return the value of the root node (max value) and remove it from the heap.
Returns: Return the value from the root node.
def
heapify_down(self, index: int):
188 def heapify_down(self, index: int): 189 """ 190 Perform heapify down starting at a given index. 191 192 Args: 193 index (int): The starting index. 194 """ 195 while self.has_left(index): 196 higher_index = self.left_index(index) 197 right_index = self.right_index(index) 198 if self.has_right(index) and self._array[right_index] > self._array[higher_index]: 199 higher_index = right_index 200 201 if self._array[index] > self._array[higher_index]: 202 break 203 else: 204 self._array[index], self._array[higher_index] = self._array[higher_index], self._array[index] 205 206 index = higher_index
Perform heapify down starting at a given index.
Args: index (int): The starting index.
def
enumerate(self):
208 def enumerate(self): 209 """ 210 Return the enumeration of a heap. 211 212 Returns: 213 Enumeration of a heap. 214 """ 215 return enumerate(self._array)
Return the enumeration of a heap.
Returns: Enumeration of a heap.
def
count(self) -> int:
217 def count(self) -> int: 218 """ 219 Return the number of items in the heap. 220 221 Returns: 222 The number of items in the heap. 223 """ 224 return len(self._array)
Return the number of items in the heap.
Returns: The number of items in the heap.
def
is_empty(self) -> bool:
226 def is_empty(self) -> bool: 227 """ 228 Check if a heap has any items. 229 230 Returns: 231 True if heap has no items. 232 False if heap has more than 0 items. 233 """ 234 return self.count() == 0
Check if a heap has any items.
Returns: True if heap has no items. False if heap has more than 0 items.
def
print(self):
236 def print(self): 237 """ 238 Print the contents of a heap. 239 """ 240 node_count = 1 241 for i in range(self.count()): 242 if i + 1 >= node_count: 243 print() 244 node_count *= 2 245 print(self._array[i], end=" ")
Print the contents of a heap.
def
to_sorted_list(self) -> list:
247 def to_sorted_list(self) -> list: 248 """ 249 Return a sorted list from the heap. 250 251 Returns: 252 A sorted list. 253 """ 254 temp_heap = Heap() 255 temp_heap._array = self._array[:] 256 257 result = [] 258 while not temp_heap.is_empty(): 259 result.append(temp_heap.pop()) 260 261 return result
Return a sorted list from the heap.
Returns: A sorted list.
279class MinHeap(Heap): 280 def heapify_up(self, index: int): 281 """ 282 Perform heapify up starting at a given index. 283 284 Args: 285 index (int): The starting index. 286 """ 287 parent_index = self.parent_index(index) 288 while self.has_parent(index) and self._array[index] < self._array[parent_index]: 289 self._array[index], self._array[parent_index] = self._array[parent_index], self._array[index] 290 index = parent_index 291 parent_index = self.parent_index(index) 292 293 def heapify_down(self, index: int): 294 """ 295 Perform heapify down starting at a given index. 296 297 Args: 298 index (int): The starting index. 299 """ 300 while self.has_left(index): 301 higher_index = self.left_index(index) 302 right_index = self.right_index(index) 303 if self.has_right(index) and self._array[right_index] < self._array[higher_index]: 304 higher_index = right_index 305 306 if self._array[index] < self._array[higher_index]: 307 break 308 else: 309 self._array[index], self._array[higher_index] = self._array[higher_index], self._array[index] 310 311 index = higher_index
A max heap implementation.
def
heapify_up(self, index: int):
280 def heapify_up(self, index: int): 281 """ 282 Perform heapify up starting at a given index. 283 284 Args: 285 index (int): The starting index. 286 """ 287 parent_index = self.parent_index(index) 288 while self.has_parent(index) and self._array[index] < self._array[parent_index]: 289 self._array[index], self._array[parent_index] = self._array[parent_index], self._array[index] 290 index = parent_index 291 parent_index = self.parent_index(index)
Perform heapify up starting at a given index.
Args: index (int): The starting index.
def
heapify_down(self, index: int):
293 def heapify_down(self, index: int): 294 """ 295 Perform heapify down starting at a given index. 296 297 Args: 298 index (int): The starting index. 299 """ 300 while self.has_left(index): 301 higher_index = self.left_index(index) 302 right_index = self.right_index(index) 303 if self.has_right(index) and self._array[right_index] < self._array[higher_index]: 304 higher_index = right_index 305 306 if self._array[index] < self._array[higher_index]: 307 break 308 else: 309 self._array[index], self._array[higher_index] = self._array[higher_index], self._array[index] 310 311 index = higher_index
Perform heapify down starting at a given index.
Args: index (int): The starting index.
Inherited Members
314class PriorityQueue(MinHeap): 315 """ 316 A priority queue implementation in Python. 317 """ 318 def push(self, priority: int, item): 319 """ 320 Insert an item with a priority into the priority queue. 321 322 Args: 323 priority (int): Priority of item. 324 item: The item to insert. 325 """ 326 super().insert((priority, item)) 327 328 def pop(self): 329 """ 330 Return and remove the highest priority value in the heap. 331 332 Returns: 333 Return The highest priority value in the heap. 334 """ 335 priority, item = super().pop() 336 return item 337 338 def pop_pair(self) -> tuple: 339 """ 340 Return and remove the highest priority value pair in the heap. 341 342 Returns: 343 Return the highest priority, value pair (tuple) in the heap. 344 """ 345 return super().pop() 346 347 def peek(self): 348 """ 349 Return the highest priority value in the heap. 350 351 Returns: 352 Return The highest priority value in the heap. 353 """ 354 priority, item = super().peek() 355 return item 356 357 def peek_pair(self) -> tuple: 358 """ 359 Return the highest priority value pair in the heap. 360 361 Returns: 362 Return the highest priority, value pair (tuple) in the heap. 363 """ 364 return super().peek() 365 366 def to_string_with_priority(self): 367 """ 368 Return string representation of a heap in order of priority. 369 """ 370 temp_array = self._array[:] 371 result = [] 372 while not self.is_empty(): 373 result.append(str(self.pop_pair())) 374 self._array = temp_array 375 376 return "[" + " ".join(result) + "]"
A priority queue implementation in Python.
def
push(self, priority: int, item):
318 def push(self, priority: int, item): 319 """ 320 Insert an item with a priority into the priority queue. 321 322 Args: 323 priority (int): Priority of item. 324 item: The item to insert. 325 """ 326 super().insert((priority, item))
Insert an item with a priority into the priority queue.
Args: priority (int): Priority of item. item: The item to insert.
def
pop(self):
328 def pop(self): 329 """ 330 Return and remove the highest priority value in the heap. 331 332 Returns: 333 Return The highest priority value in the heap. 334 """ 335 priority, item = super().pop() 336 return item
Return and remove the highest priority value in the heap.
Returns: Return The highest priority value in the heap.
def
pop_pair(self) -> tuple:
338 def pop_pair(self) -> tuple: 339 """ 340 Return and remove the highest priority value pair in the heap. 341 342 Returns: 343 Return the highest priority, value pair (tuple) in the heap. 344 """ 345 return super().pop()
Return and remove the highest priority value pair in the heap.
Returns: Return the highest priority, value pair (tuple) in the heap.
def
peek(self):
347 def peek(self): 348 """ 349 Return the highest priority value in the heap. 350 351 Returns: 352 Return The highest priority value in the heap. 353 """ 354 priority, item = super().peek() 355 return item
Return the highest priority value in the heap.
Returns: Return The highest priority value in the heap.
def
peek_pair(self) -> tuple:
357 def peek_pair(self) -> tuple: 358 """ 359 Return the highest priority value pair in the heap. 360 361 Returns: 362 Return the highest priority, value pair (tuple) in the heap. 363 """ 364 return super().peek()
Return the highest priority value pair in the heap.
Returns: Return the highest priority, value pair (tuple) in the heap.
def
to_string_with_priority(self):
366 def to_string_with_priority(self): 367 """ 368 Return string representation of a heap in order of priority. 369 """ 370 temp_array = self._array[:] 371 result = [] 372 while not self.is_empty(): 373 result.append(str(self.pop_pair())) 374 self._array = temp_array 375 376 return "[" + " ".join(result) + "]"
Return string representation of a heap in order of priority.