문인철 교수님의 ‘Non-Linear Structure, Optimization, and Algorithms’ 수업

Priority Queue

Enqueue 를 하지만 prioirty 를 설정 해야한다.
- higher value
- lower value

Implementation & performance of priority Queue

How?

linked list
element, priority 를 저장
Lazy approach == unsorted implementation - Dequeue 할때 뒤늦게 sorting 을 하는 경우 - enqueue 를 실행 할때 기존 queue 와 동일함
Early bird approach == Sorted implementation - enqueue 할때 sorting 이 일어남 - 저장되어있을 때 항상 정렬이 일어나있음

코드

Enqueue 할때 priority 를 설정해야함

class Node:
    next_node = None
    prev_node = ''
    value = ''
    is_head = False
    is_tail = False

    def __init__(self, value = '', next_node = None,
                    is_head = False, is_tail = False):
        self.next_node = next_node
        self.value = value
        self.is_head = is_head
        self.is_tail = is_tail

    def get_value(self):
        return self.value

    def set_value(self, value):
        self.value = value

    def get_next(self):
        return self.next_node

    def set_next(self, next_node):
        self.next_node = next_node

    def is_head(self):
        return self.is_head

    def is_tail(self):
        return self.is_tail
    
class SinglyLinkedList:
    node_head = ''
    node_tail = ''
    size = 0 
    def __init__(self):
        self.node_tail = Node(is_tail=True)
        self.node_head = Node(is_head=True, next_node=self.node_tail)
    
    def insert_node(self, value, index):
        new_node = Node(value = value)
        prev_node = self.get(index - 1)
        next_node = prev_node.get_next()
        prev_node.set_next(new_node)
        new_node.set_next(next_node)
        self.size += 1
    
    def remove_node(self, index_to_remove):
        prev_node = self.get(index_to_remove - 1)
        node_to_remove = prev_node.get_next()
        next_node = node_to_remove.get_next()
        prev_node.set_next(next_node)
        self.size -= 1
        return node_to_remove
    
    def get(self, index):
        result_node = self.node_head
        for i in range(index + 1):
            result_node = result_node.get_next()
        return result_node
    
    def get_size(self):
        return self.size
    
    def print_status(self):
        current_node = self.node_head
        while current_node.get_next().is_tail == False:
            current_node = current_node.get_next()
            print(f'{current_node.get_value()} > ', end = "")

class PriorityNode:
    priority = -1 
    value = ''
    
    def __init__(self, value, priority):
        self.priority = priority
        self.value = value
        
    def get_value(self):
        return self.value
    
    def get_priority(self):
        return self.priority
    
class PriorityQueue:
    list = ''
    
    def __init__(self):
        self.list = SinglyLinkedList()
    
    def enqueue_with_priority(self, value, priority):
        idx_insert = 0 
        for i in range(self.list.get_size()):
            node = self.list.get(i)
            
            if node.get_value() == '':
                idx_insert = i
                break
            if node.get_value().get_priority() < priority:
                idx_insert = i 
                break
            else:
                idx_insert = i + 1
            
        self.list.insert_node(PriorityNode(value, priority), idx_insert)
    
    def dequeue_with_priority(self):
        return self.list.remove_node(0).get_value().value