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

## Similar Samples

Check out our programming homework samples to see the quality of our solutions. Each example demonstrates our expertise in various programming languages and our commitment to providing accurate, detailed work. See how we can help you excel in your programming assignments.

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python