ben martin - 1 year ago 82

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).

Answer

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

Source (Stackoverflow)