ben martin - 2 years ago 139

Python Question

`from myNode import *`

from tasks import *

class PriorityQueue():

__slots__ = ( 'front', 'back', 'size' )

def mkPriorityQueue():

queue = PriorityQueue()

queue.front = NONE_NODE

queue.back = NONE_NODE

queue.size = 0

return queue

def insert(queue, element):

newnode = mkNode(element, NONE_NODE)

if emptyQueue(queue):

#if the queue was empty, the new node is now both the first and last one

queue.front = newnode

queue.back = newnode

elif frontMax(queue).priority > newnode.data.priority:

#if the new node has a higher priority than the first, insert at front

newnode.next = queue.front #old first is now second node

queue.front = newnode

else:

#the node has a lower priority than the first

#find the next node with a lower priority, insert newnode before that

currentnode = queue.front

while not currentnode.next == NONE_NODE:

#traverse nodes until we find a lower priority or until the end

if currentnode.next.data.priority < newnode.data.priority:

break

currentnode = currentnode.next

#insert newnode between currentnode and currentnode.next

newnode.next = currentnode.next

currentnode.next = newnode

#if newnode.next is now NODE_NONE, we're at the end so change backMin

if newnode.next == NONE_NODE:

queue.back = newnode

queue.size += 1

def removeMax(queue):

"""Remove the front element from the queue (returns None)"""

if emptyQueue(queue):

raise IndexError("Cannot dequeue an empty queue")

queue.front = queue.front.next

if emptyQueue(queue):

queue.back = NONE_NODE

queue.size -= 1

def frontMax(queue):

"""Access and return the first element in the queue without removing it"""

if emptyQueue(queue):

raise IndexError("front on empty queue")

return queue.front.data

def backMin(queue):

"""Access and return the last element in the queue without removing it"""

if emptyQueue(queue):

raise IndexError("back on empty queue")

return queue.back.data

def emptyQueue(queue):

"""Is the queue empty?"""

return queue.front == NONE_NODE

Am I doing that right? Below is that problem I am trying to solve. I have added all the function(s) I did.

inserts (Under the Insert Function) it using the priority rules (Each task has an integer priority from 10

(highest priority) to 1 (lowest priority). If two tasks have the same priority, the order should be based on the

order they were inserted into the priority queue (earlier ﬁrst).

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

First of all, you've got a syntax error on your `else`

statement which does not take a test expression. Besides that, your logic is off as it would not maintainin the correct node structure in `insert`

- when you do `queue.firstMax = newnode`

, you basically delete the current `firstMax`

element as you no longer have a reference to it; you'll need to assign the old first element to `newnode.next`

in this case. Also, if the priority of the new task is `<=`

the current first, you'll need to traverse the queue to find the correct place for the new node to maintain the order - it's supposed to go before the first element with a lower priority. (In an optimized implementation, you would store the nodes separated by priority, or at least keep a reference to the last nodes of each priority, to speed up this insertion, but I guess this is outside the scope of this exercise.)

Here's an implementation of `insert`

which should perform correctly:

```
def insert(queue, element):
newnode = mkNode(element, NONE_NODE)
if emptyQueue(queue):
#if the queue was empty, the new node is now both the first and last one
queue.frontMax = newnode
queue.backMin = newnode
elif frontMax(queue).priority > newnode.data.priority:
#if the new node has a higher priority than the first, insert at front
newnode.next = queue.frontMax #old first is now second node
queue.frontMax = newnode
else:
#the node has a lower priority than the first
#find the next node with a lower priority, insert newnode before that
currentnode = queue.frontMax
while not currentnode.next == NODE_NONE:
#traverse nodes until we find a lower priority or until the end
if currentnode.next.data.priority < newnode.data.priority:
break
currentnode = currentnode.next
#insert newnode between currentnode and currentnode.next
newnode.next = currentnodenode.next
currentnode.next = newnode
#if newnode.next is now NODE_NONE, we're at the end so change backMin
if newnode.next == NODE_NONE:
queue.backMin = newnode
queue.size += 1
```