ben martin ben martin - 7 months ago 29
Python Question

Python Insert using Priority

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

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
Comments