우선순위 큐

우선순위 큐

높은 우선순위(priority)를 가지는 데이터들이 먼저 나가는 우선순위 큐는 배열, 연결 리스트, 히프 등을 이용해 구현이 가능한데 그 중 히프 자료구조를 이용하여 구현하는것이 O(logn) 으로 제일 효율적이다.

소스코드

from heap import maxHeap

class priority_queue():
    def __init__(self, max_size):
        self.max_size = max_size    
        self.maxH = maxHeap(max_size)

    def is_empty(self):
        if self.maxH.heap_size == 0:
            return True 
        else:
            return False 

    def is_full(self):
        if self.maxH.heap_size >= self.max_size-1:
            return True
        else:
            return False

    def insert(self, item):
        if self.is_full():
            print("heap is full")
        else:
            self.maxH.insert(item)

    def delete(self):
        if self.is_empty():
            return "heap is empty"
        else:
            return self.maxH.delete()

    def find(self):
        if self.is_empty():
            return "heap is empty"
        else:
            return self.maxH.heap[1]

if __name__ == "__main__":
    pq = priority_queue(200)
    pq.insert(10)
    pq.insert(5)
    pq.insert(30)
    print(pq.delete())
    print(pq.delete())
    print(pq.delete())
    print(pq.find())

출력

30
10
5
heap is empty