I am implementing a priority queue using a max-heap data structure in Python. I'm using several names that have numbers associated with them as their priority (9 being the highest and 1 being the lowest). The issue I am facing is that when I dequeue an item from the priority queue, it does not dequeue the item with highest priority. I assume this means there is a problem with my enqueue and it is not inserting the items into the correct position in the heap based on their priority. If anyone could help me fix this, it would be greatly appreciated.
My priority queue code:
from Heap import Heap
class priorityQ(object):
def __init__(self):
self.PQ = Heap()
def enqueue(self, priority, item):
self.PQ.insert((priority, item))
def dequeue(self):
if self.PQ.size() == 0:
raise ValueError("Empty Queue")
return self.PQ.delete_max()
def first(self):
return self.PQ.get_max()
def size(self):
return self.PQ.size()
def main():
myHeap = priorityQ()
print(myHeap.size())
myHeap.enqueue(8, "Kaneda")
myHeap.enqueue(6, "Masaru")
myHeap.enqueue(9, "Akira")
myHeap.enqueue(4, " Kei")
myHeap.enqueue(5, "Takashi")
myHeap.enqueue(2, "Shikishima")
myHeap.enqueue(3, "Kiyoko")
myHeap.enqueue(1, "Yamagata")
myHeap.enqueue(7, "Tetsuo")
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
myHeap.dequeue()
print(myHeap.first())
print(myHeap.size())
Output after I run the code and call main:
0
(9, 'Akira')
9
(7, 'Tetsuo')
8
(5, 'Takashi')
7
(4, 'Kei')
6
(3, 'Kiyoko')
5
(2, 'Shikishima')
4
(1, 'Yamagata')
3
(1, 'Yamagata')
2
(1, 'Yamagata')
1
None
0
Max-heap code (provided by textbook):
# Heap.py
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 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 right child, determine 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 get_max(self):
if self.heap_size > 0:
max_item = self.heap[1]
self.heap[1] = self.heap[self.heap_size]
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 item down
self.heap[position] = self.heap[parent]
position = parent
parent = position // 2
# put new item in 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
Your problem seems to be in your enqueue.
def enqueue(self, item, priority):
self.PQ.insert(item)
The priority parameter is not used at all. Instead, your heap is using string comparisons.
This is the state of your heap before any dequeue:
[None, 'Yamagata', 'Tetsuo', 'Shikishima', 'Takashi', 'Masaru', 'Akira', 'Kiyoko', 'Kei', 'Kaneda']