I am new to Python and wanted to make sure my code answers the question for my assignment due.
My Task:
A priority queue is a queue in which each item is assigned a priority and items with a higher priority are removed before those with a lower priority, irrespective of when they were added. Integer values are used for the priorities with a smaller integer value having a higher priority. In an unbounded priority queue, there are no limits on the range of integer values that can be used for the priorities.
• PriorityQueue()
: Creates a new empty unbounded priority queue.
• isEmpty()
: Returns a boolean value indicating whether the queue is empty.
• length()
: Returns the number of items currently in the queue.
• enqueue(item, priority)
: Adds the given item to the queue by inserting it in the proper position based on the given
priority.
• dequeue()
: Removes and returns the next item from the queue, which is the item with the highest priority.
If two or more items have the same priority, those items are removed in FIFO order. An item cannot be dequeued from an empty queue.
• peek()
: Returns a copy of the next item in the queue, without removing the item. The next item is the same value that would be returned by the dequeue operation. An item cannot be dequeued from an empty queue.
My Code:
class Node( object ) :
def __init__( self, cargo = None, next = None ) :
self.cargo = cargo
self.next = next
# Creates a new empty unbounded priority queue
class PriorityQueue :
#
def __init__( self ) :
self.length = 0
self.head = None
self.last = None
# Returns a boolean value indicating whether the queue is empty
def isEmpty( self ) :
return (self.length == 0)
# Returns the number of items currently in the queue
def __len__( self ) :
return len(self.length)
# Adds the given item to the queue by inserting it in the proper position
# based on the given priority. The new node is appeneded to the end of the
# linked list
def enqueue( self, item, priority) :
newNode = Node(cargo)
newNode.next = None
if self.length == 0:
self.head self.last = newNode
newNode.next = self.head
self.head = newNode
self.last.next = newNode
self.last = newNode
temp = self.head
p = self.head.next
while p != None :
if p.cargo > newNode.cargo:
temp = temp.next
p = p.next
break
newNode.next = temp.next
temp.next = newNode
# Removes and returns the next item from the queue, which is the item with
# the highest priority. If two or more items have the same priority, those
# items are removed in FIFO order. An item cannot be dequeued from an
# empty queue. The linked list is searched to find the entry with the
# highest priority.
def dequeue( self ) :
cargo = self.head.cargo
self.head = self.head.next
self.length = self.length - 1
if self.length == 0:
self.last = None
return cargo
-
\$\begingroup\$ It's unrealistic to do a thorough code review if your code is due tomorrow. We're glad you found the site, and I'm sure you'll get some good answers, but for now I would suggest to test for correctness so that you don't turn in some incorrect code for your assignment. \$\endgroup\$Phrancis– Phrancis2015年04月15日 01:10:27 +00:00Commented Apr 15, 2015 at 1:10
-
\$\begingroup\$ @sᴉɔuɐɹɥԀ Sorry I meant to put Thursday, my computer autotyped. \$\endgroup\$Lindsey– Lindsey2015年04月15日 01:14:40 +00:00Commented Apr 15, 2015 at 1:14
-
\$\begingroup\$ OK. I made a few edits to make your question a bit better formatted. Hope you get some great answers! \$\endgroup\$Phrancis– Phrancis2015年04月15日 01:21:08 +00:00Commented Apr 15, 2015 at 1:21
2 Answers 2
A Priority Queue is synonymous with a heap so I'm assuming that the implication in this assignment was to implement a maximally efficient data structure.
The optimal implementation is spelled out in Wikipedia: http://en.m.wikipedia.org/wiki/Heap_(data_structure)
If it were me, I would use a tree instead of a list. There is no Node class. A Heap object has two nullable Heap children, and every operation is recursive in nature. Length, for example, would just return each child's length or 1 if no children existed. The other operations would take advantage of the tree's structure in order to return results in logarithmic time.
-
\$\begingroup\$ Python has a built-in heap implementation (see the
heapq
module) so it would make sense to use that and not write your own. Also, Python doesn't have "nullable" types as such — perhaps you are thinking of C#? \$\endgroup\$Gareth Rees– Gareth Rees2015年04月15日 11:53:44 +00:00Commented Apr 15, 2015 at 11:53 -
\$\begingroup\$ Yes, you are correct on both fronts. I meant "nullable" in the sense that the reference will either be a Heap or None \$\endgroup\$Scott Lobdell– Scott Lobdell2015年04月15日 16:00:43 +00:00Commented Apr 15, 2015 at 16:00
-
\$\begingroup\$ my assignment specifically says to use linked lists!!!! \$\endgroup\$Lindsey– Lindsey2015年04月15日 18:27:04 +00:00Commented Apr 15, 2015 at 18:27
You are not using a priority variable for prioritizing the order of elements in the queue. Also, there are subtle issues in the code which can be fixed. Please find the below code:-
# Python code to implement Priority Queue using Linked List
# Node class
class Node:
def __init__(self, item, priority):
self.item = item
self.next = None
self.priority = priority
class PriorityQueue:
def __init__(self):
self.front = self.rear = None
# Returns a boolean value indicating whether the queue is empty
def isEmpty(self):
return self.front == None
# Adds the given item to the queue by inserting it in the proper
# position based on the given priority. The new node is appended to
# the end of the linked list
def enqueue(self, item, priority):
newNode = Node(item, priority)
if not self.rear:
self.front = self.rear = newNode
return
if self.front.priority < newNode.priority:
newNode.next = self.front
self.front = newNode
return
previous = None
current = self.front
while(current and newNode.priority < current.priority):
previous = current
current = current.next
if current:
previous.next = newNode
newNode.next = current
else:
self.rear.next = newNode
self.rear = newNode
# Removes and returns the next item from the queue, which is the
# item with the highest priority. If two or more items have the
# same priority, those items are removed in FIFO order. An item
# cannot be dequeued from an empty queue.
def dequeue(self):
if self.isEmpty():
print('Queue is empty')
return
temp = self.front
self.front = self.front.next
if self.front == None:
self.rear = None
return temp.item
-
1\$\begingroup\$ Welcome to Code Review and thanks for offering an answer! Would you please explicitly state above the code what you changed from the OP’s code and what justification makes it better? Please read Why are alternative solutions not welcome? \$\endgroup\$2018年09月08日 09:44:03 +00:00Commented Sep 8, 2018 at 9:44
-
\$\begingroup\$ You have presented an alternative solution, but barely reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$2018年09月08日 13:44:13 +00:00Commented Sep 8, 2018 at 13:44