Related Topics
Data Structure
class Node:
def __init__(self, value):
self.value = value
self.next = None
class Queue:
def __init__(self):
self.front = None
self.rear = None
def enqueue(self, value):
new_node = Node(value)
if not self.rear:
self.front = new_node
self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if not self.front:
return None
value = self.front.value
if self.front == self.rear:
self.front = None
self.rear = None
else:
self.front = self.front.next
return value
def peek(self):
if not self.front:
return None
return self.front.value
def is_empty(self):
return self.front is None
In this implementation, the Queue class has two instance variables front and rear that point to the front and rear of the queue, respectively. When we enqueue a new element into the queue, we create a new node with the given value and set its next attribute to None. If the queue is empty, we set both front and rear to be the new node. Otherwise, we set the next attribute of the current rear node to be the new node, and update rear to point to the new node. When we dequeue an element from the queue, we return the value of the front node and update front to point to the next node in the queue. If the queue becomes empty after the dequeue, we set both front and rear to be None. The peek method returns the value of the front node without removing it from the queue. Finally, the is_empty method checks if the front node is None to determine if the queue is empty.
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
self.index = 0
def push(self, item, priority):
heapq.heappush(self.heap, (priority, self.index, item))
self.index += 1
def pop(self):
return heapq.heappop(self.heap)[-1]
In this implementation, we use the built-in heapq module in Python to create a min-heap. The push method takes two arguments: the item to be inserted and its priority. We add the item to the heap as a tuple with three elements: its priority, an index value that is incremented for each insertion, and the item itself. The use of the index value ensures that items with the same priority are dequeued in the order in which they were added. The pop method removes and returns the item with the highest priority from the heap.
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self):
self.root = None
def insert(self, key, value):
self.root = self._insert(self.root, key, value)
def _insert(self, node, key, value):
if node is None:
return Node(key, value)
if key < node.key:
node.left = self._insert(node.left, key, value)
elif key > node.key:
node.right = self._insert(node.right, key, value)
else:
node.value = value
return node
def search(self, key):
node = self.root
while node is not None:
if key < node.key:
node = node.left
elif key > node.key:
node = node.right
else:
return node.value
return None
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if node is None:
return None
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
else:
successor = self._min_node(node.right)
node.key = successor.key
node.value = successor.value
node.right = self._delete(node.right, successor.key)
return node
def _min_node(self, node):
while node.left is not None:
node = node.left
return node
In this implementation, we define a Node class to represent each node in the tree, with key and value attributes for the key-value pairs. We also define a BST class to represent the entire tree, with methods for insertion, searching, and deletion.
The insert method takes a key and a value and inserts them into the tree, following the BST property. The _insert method is a helper function that recursively inserts the new node into the correct position in the tree.
The search method takes a key and returns the corresponding value in the tree, if it exists. The _delete method deletes a node with the given key from the tree, also following the BST property. If the node has two children, we find the successor node (i.e., the node with the smallest key in its right subtree) and replace the current node’s key and value with the successor’s key and value before deleting the successor node.
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.