Program To Solve Data Structures and Algorithms In Python Assignment Solution.

Instructions

Objective

Write a python homework program to solve data structures and algorithms.

Requirements and Specifications

Data Structures Algorithms Assignment

Please follow the instruction and submit the coding file. Also, please submit one page writing explanation in Word document.

Your submission should be accompanied by a one page explanation‐through of your code. The one page analysis should include your decision making process, the logic behind you code, an your original thoughts that went into the decision making on why your code is written and performs in the manner in which you have written it.

Assignment: Heaps

You have been provided a Python file, heap.py, which constructs a heap structure with a list. Using that code as a guide:

• Develop a heap data structure using a linked structure (Nodes and Pointers)
• The heap must support add and remove from the heap
• All operations most abide by the rules that govern a heap (see lecture slides for reference)

Once you have your heap structure created, next you must use it as a backing structure to a priority queue.

• Develop a priority queue data structure that is backed by a heap (linked structure NOT A LIST)
• Implement the normal methods that accompany a priority queue structure
• Enqueue, dequeue, and peek by priority not position
• Also length and whether or not the structure is empty (is_empty)
• Perform the following operations to showcase your working structure
• Enqueue the following items: 4, 7, 5, 11, 8, 6, 9
• Dequeue 3 items by priority, they should be 4, 5, & 6.

Source Code

HEAP class Heap: class _HeapNode: def __init__(self, key): self._key = key self._parent = None self._left = None self._right = None def get_key(self): return self._key def set_key(self, key): self._key = key def __lt__(self, other): return self._key < other.get_key() def __gt__(self, other): return self._key > other.get_key() def set_parent(self, node): self._parent = node def set_left(self, node): self._left = node def set_right(self, node): self._right = node def get_parent(self): return self._parent def get_left(self): return self._left def get_right(self): return self._right def __init__(self): self._root = None self._size = 0 def _find_last(self, is_pos): if self._size == 0: return None path = [] curr_code = self._size while curr_code > 0: path.insert(0, curr_code % 2) curr_code = int(curr_code / 2) path.pop(0) curr_node = self._root j = 0 while j < len(path): if path[j] == 0: if j == len(path) - 1 and is_pos: break curr_node = curr_node.get_left() else: if j == len(path) - 1 and is_pos: break curr_node = curr_node.get_right() j += 1 if j == len(path) - 1 and is_pos: return [curr_node, path[j]] return curr_node @staticmethod def _swap(node1, node2): sw = node1.get_key() node1.set_key(node2.get_key()) node2.set_key(sw) def _upheap(self, node): parent = node.get_parent() if parent is not None and parent > node: self._swap(parent, node) self._upheap(parent) def _downheap(self, node): if node.get_left() is not None: if node.get_right() is not None: if node.get_left() < node.get_right() and node.get_left() < node: self._swap(node, node.get_left()) self._downheap(node.get_left()) elif node.get_left() > node.get_right() and node.get_right() < node: self._swap(node, node.get_right()) self._downheap(node.get_right()) else: if node.get_left() < node: self._swap(node, node.get_left()) self._downheap(node.get_left()) else: if node.get_right() is not None: if node.get_right() < node: self._swap(node, node.get_right()) self._downheap(node.get_right()) def is_empty(self): return self._root is None def add(self, key): new_node = self._HeapNode(key) self._size += 1 if self._root is None: self._root = new_node return result = self._find_last(True) if result[1] == 0: result[0].set_left(new_node) else: result[0].set_right(new_node) new_node.set_parent(result[0]) self._upheap(new_node) def min(self): if self._root is None: return None return self._root.get_key() def remove_min(self): if self._root is None: return None old_min = self.min() last = self._find_last(False) self._swap(self._root, last) last_parent = last.get_parent() self._size -= 1 if last_parent is None: self._root = None return old_min else: if last_parent.get_left() == last: last_parent.set_left(None) else: last_parent.set_right(None) self._downheap(self._root) return old_min def __str__(self): queue = [] out = [] if self._root is not None: queue.append(self._root) while len(queue) > 0: node = queue.pop(0) out.append(node.get_key()) if node.get_left() is not None: queue.append(node.get_left()) if node.get_right() is not None: queue.append(node.get_right()) return ", ".join(map(lambda v : str(v), out)) PRIORITY QUEUE from Heap import Heap class PriorityQueue: def __init__(self): self._heap = Heap() def enqueue(self, item): return self._heap.add(item) def dequeue(self): return self._heap.remove_min() def peek(self): return self._heap.min() def is_empty(self): return self._heap.is_empty() def __str__(self): return str(self._heap) pq = PriorityQueue() print(pq) pq.enqueue(4) print(pq) pq.enqueue(7) print(pq) pq.enqueue(5) print(pq) pq.enqueue(11) print(pq) pq.enqueue(8) print(pq) pq.enqueue(6) print(pq) pq.enqueue(9) print(pq) for _ in range(0,3): print(pq.dequeue()) print(pq)