우선 순위 큐 (Priority Queues)

우선순위 큐

무조건 선입선출의 개념에 의한 것이 아닌, 우선순위가 높은 순서대로 dequeue 되는 것을 의미한다.이는 운영체제에서 CPU 스케줄러를 구현에서 사용하고 전공 강의에서 접해본 적이 있다.

우선순위 큐는 크게 두가지 접근 방법이 있다.
1. 큐에 원소를 넣을 때 (enqueue 할 때) 우선순위 순서대로 정렬해 두는 방법
2. 큐에서 원소를 꺼낼 때 (dequeue 할 때) 우선순위가 가장 높은 것을 선택하는 방법

1번, enqueue할 경우 우선순위 순서대로 정렬해 두는 방법이 복잡도 차원에서 좀 더 유리하다. 그 이유는 이미 큐를 정렬 상태로 두기 때문에 우선순위에 따라 큐를 정렬하기 위한 삽입 연산을 줄일 수 있기 때문이다. 즉, 이미 정렬 되어 있기에 큐의 모든 원소의 우선순위를 조회할 필요가 없기 때문이다.

실습

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None

class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s

    def getLength(self):
        return self.nodeCount

    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result

    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result

    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr

    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)

    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)

    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail

        self.nodeCount += L.nodeCount

class PriorityQueue:

    def __init__(self):
        self.queue = DoublyLinkedList()

    def size(self):
        return self.queue.getLength()

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, x):
        newNode = Node(x)
        curr =  self.queue.head
        while curr.next.data != None and  curr.next.data > newNode.data :
            curr = curr.next
        self.queue.insertAfter(curr, newNode)

    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data

def solution(x):
    return 0

curr.next.data != None 이 부분을 curr.next != None으로 설정해서 런타임 에러가 발생했다. curr.next != None로 하게되면 결국 curr.tail.next 까지 도달하게 된 후에 해당 조건이 False가 될 것이다. tail까지 도달하게 되면 curr.next.data (None) , newNode.data (int) 이기 때문에 타입에러가 발생하게 되서 코드가 실행되지 않는 것이었다.

이를 수정한뒤 insertAfter를 이용하여 우선순위에 맞게 연결 노드가 정렬되었다.(숫자가 낮을 수록 우선순위가 높음)

저작자표시 비영리

우선순위 큐

실습

티스토리툴바