Program To Solve Data Structures and Algorithms in Python

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)

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

Instructions

Requirements and Specifications