Вставка питона с использованием приоритета

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 

Я делаю это правильно? Ниже я пытаюсь решить эту проблему. Я добавил все функции, которые я сделал.

Вставка (в функции Insert) используется с использованием правил приоритета (каждая задача имеет целочисленный приоритет от 10 (наивысший приоритет) до 1 (самый низкий приоритет). Если две задачи имеют одинаковый приоритет, порядок должен основываться на , чтобы они были вставлены в очередь приоритетов (ранее в начале).

Answer 1

Прежде всего, у вас есть синтаксическая ошибка в вашем операторе else, который не принимает тестовое выражение. Кроме того, ваша логика выключена поскольку он не будет поддерживать правильную структуру узла в insert - когда вы делаете queue.firstMax = newnode, вы в основном удаляете текущий элемент firstMax, поскольку у вас больше нет ссылки на него, вы будете в этом случае необходимо назначить старый первый элемент newnode.next. Кроме того, если приоритет новой задачи равен <= текущей, вам нужно пройти очередь, чтобы найти нужное место для нового узла для поддержания порядка - он должен идти до первого элемента с более низким приоритетом. (В оптимизированной реализации вы сохранили бы узлы, разделенные приоритетом, или, по крайней мере, сохранили ссылку на последние узлы каждого приоритета, чтобы ускорить эту вставку, но я думаю, что это выходит за рамки этого упражнения.)

Вот реализация insert, который должен выполнять правильно:

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