This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def size(self) -> int: | |
"""Traverses the linked list and returns the number of nodes in it""" | |
if self.is_empty(): | |
return 0 | |
size = 0 | |
current_node = self.head | |
while current_node is not None: | |
current_node = current_node.next_node | |
size += 1 | |
return size |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from typing import Any, Union | |
class Node: | |
"""A linked list node implementation""" | |
def __init__(self, node_data: Any) -> None: | |
"""Initialize the node with the given data and pointing to None""" | |
self._data = node_data | |
self._next_node = None |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from typing import Any, Union | |
class Node: | |
"""A linked list node implementation""" | |
def __init__(self, node_data: Any) -> None: | |
"""Initialize the node with the given data and pointing to None""" | |
self._data = node_data | |
self._next_node = None |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import heapq | |
from typing import Union | |
class PriorityQueue: | |
"""A priority queue implementation based on heapq""" | |
insertion_count = 0 | |
def __init__(self) -> None: |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def is_empty(self) -> bool: | |
"""Returns True is the priority queue is empty""" | |
return not self.pqueue |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def insert(self, task: str, priority: int) -> None: | |
"""Add an item to the priority queue""" | |
heapq.heappush(self.pqueue, (priority, self.insertion_count, task)) | |
self.insertion_count += 1 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def pull(self) -> Union[str, None]: | |
""" | |
Return and remove the task with the highest priority. | |
Since Python's heapq is implemented as a min heap, a | |
smaller number mean the higher priority, i.e. priority 1 | |
has a higher priority that priority 2. | |
Elements with same priority are pulled in the order of | |
insertion. | |
""" |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def peek(self) -> Union[str, None]: | |
"""Return the task with the highest priority""" | |
if self.is_empty(): | |
return None | |
return self.pqueue[0][2] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def size(self) -> int: | |
"""Return the number of items in the priority queue""" | |
return len(self.pqueue) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import heapq | |
from typing import Union | |
class PriorityQueue: | |
"""A priority queue implementation based on heapq""" | |
insertion_count = 0 | |
def __init__(self) -> None: |