# 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)```