I am having real trouble using my custom-made heap class functions to be used in my Priority Queue class. I am having trouble on what functions from my heap class to use for my "enqueue", "dequeue", "front" and "size" functions for my PriorityQueue. I know for "enqueue" I need to use my insert function, but I don't know how to go about this because I have a priority. Could someone help me out what I need to do in order to make my PriorityQueue class to use the functions from my Heap class in order to work properly? I have been stuck on this for awhile and I keep finding answers that include using the built in python functions such as queue and heapq.
class Heap(object):
def __init__(self, items=None):
'''Post: A heap is created with specified items.'''
self.heap = [None]
if items is None:
self.heap_size = 0
else:
self.heap += items
self.heap_size = len(items)
self._build_heap()
def size(self):
'''Post: Returns the number of items in the heap.'''
return self.heap_size
def _heapify(self, position):
'''Pre: Items from 0 to position - 1 satisfy the Heap property.
Post: Heap Property is satisfied for the entire heap.'''
item = self.heap[position]
while position * 2 <= self.heap_size:
child = position * 2
# If the right child, determine the maximum of two children.
if (child != self.heap_size and self.heap[child+1] > self.heap[child]):
child += 1
if self.heap[child] > item:
self.heap[position] = self.heap[child]
position = child
else:
break
self.heap[position] = item
def delete_max(self):
'''Pre: Heap property is satisfied
Post: Maximum element in heap is removed and returned. '''
if self.heap_size > 0:
max_item = self.heap[1]
self.heap[1] = self.heap[self.heap_size]
self.heap_size -= 1
self.heap.pop()
if self.heap_size > 0:
self._heapify(1)
return max_item
def insert(self, item):
'''Pre: Heap Property is Satisfied.
Post: Item is inserted in proper location in heap.'''
self.heap_size += 1
# extend the length of the list.
self.heap.append(None)
position = self.heap_size
parent = position // 2
while parent > 0 and self.heap[parent] < item:
# Move the item down.
self.heap[position] = self.heap[parent]
position = parent
parent = position // 2
# Puts the new item in the correct spot.
self.heap[position] = item
def _build_heap(self):
''' Pre: Self.heap has values in 1 to self.heap_size
Post: Heap property is satisfied for entire heap. '''
# 1 through self.heap_size.
for i in range(self.heap_size // 2, 0, -1): # Stops at 1.
self._heapify(i)
def heapsort(self):
'''Pre: Heap Property is satisfied.
Post: Items are sorted in self.heap[1:self.sorted_size].'''
sorted_size = self.heap_size
for i in range(0, sorted_size -1):
# Since delete_max calls pop to remove an item, we need to append a dummy value to avoid an illegal index.
self.heap.append(None)
item = self.delete_max()
self.heap[sorted_size - i] = item
So this is working but like I previously stated I am having trouble on how to make a priority queue out of this? I know asking for code is wrong, but I'm desperate could anyone help me out here? I have the basic rundown on what I want my priority code to do..
#PriorityQueue.py
from MyHeap import Heap
class PriorityQueue(object):
def __init__(self):
self.heap = None
def enqueue(self, item, priority):
'''Post: Item is inserted with specified priority in the PQ.'''
self.heap.insert((priority, item))
def first(self):
'''Post: Returns but does not remove the highest priority item from the PQ.'''
return self.heap[0]
def dequeue(self):
'''Post: Removes and returns the highest priority item from the PQ.'''
if self.heap is None:
raise ValueError("This queue is empty.")
self.heap.delete_max()
def size(self):
'''Post: Returns the number of items in the PQ.'''
return self.size
This is what I got so far but I do not know if it is entirely correct. Could anyone help me out?
I edited my code to the most current version of it.
Since this is presumably homework, all I can do is give hints, which is often easier done as comments. Since this ended up being a fairly thorough series of hints I'm summarizing them as an answer here.
For the most part, methods in your PriorityQueue class will map to methods you've already implemented in your Heap class:
PriorityQueue.enqueue() maps pretty easily to Heap.insert()PriorityQueue.first() does not have a corresponding heap method, but can still be implemented in one line. You just need to return the maximum value, which will always be at a specific place in your heap. PriorityQueue.dequeue() is a little more complicated. It needs to save the value of the top item first so that it can return it after calling heap.delete_max()size() method, which PriorityQueue.size() can call, instead of maintaining a separate size variable within the PriorityQueue class.Additionally, you need an init function, This should create a new Heap object that will be maintained by the class.
In order to make an iterator, you'll need to make a new class. It will need to maintain an integer variable (let's call it self.index), indicating its current place in the queue. You'll also want a method that increases self.index and returns the value that was at the previous index location. That should be about it.