queue - 3

우선순위 큐에 대해 구현해보자. 보통 우선순위 큐는 heap정렬 알고리즘을 이용해 구현하지만 heap을 이용하지 않고 우선순위 큐를 구현해보겠다. 

우선순위 큐란 모든 데이터가 우선순위를 가지고 있고 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력되는 구조이다. 즉 내림차순 정렬이라고 생각하면 된다.

우선순위 큐는 어떤 요소가 먼저 삭제되는가에 따라 최대 우선순위 큐와 최소 우선순위 큐로 나누어진다. 보통은 최대 우선순위 큐를 사용한다.(우선순위 높은 데이터가 먼저 삭제되는)

우선순위 큐는 다른 큐들과 다른 점이 일렬로 나열되어 있지 않다는 것이다. 우선순위 큐는 한 순간에 가장  우선순위가 높은 항목만 알 수 있으면 된다.

이를 heap이 아닌 list를 통해 구현해보겠다.

class PriorityQueue:
    def __init__(self):
        self.items=[]
    def isEmpty(self):
        return len(self.items) == 0
    def size(self): return len(self.items)
    def clear(self) : self.items=[]
    def enqueue(self,item):
        self.items.append(item) # list 맨 뒤에 삽입
    def findMaxIndex(self): # 최대 우선순위 항목의 인덱스 반환
        if self.isEmpty():return None
        else:
            highest = 0 # 일단 0을 최대라 하고
            for i in range(1,self.size()): # 모든 항목에 대해
                if self.items[i]>self.items[highest]:
                    highest = i # 최고 우선순위 인덱스 갱신
        return highest
    def dequeue(self): # 삭제
        highest = self.findMaxIndex() # 우선순위가 가장 높은 항목 삭제
        if highest is not None:
            return self.items.pop(highest)
    def peek(self): # 삭제하지 않고 그냥 반환
        highest = findMaxIndex()
        if highest is not None:
            return self.items[highest]

init과 isEmpty ,size ,clear는 스택이나 큐를 구현할 때와 거의 비슷하다.

삽입 함수 enqueue는 append함수를 사용하여 시간복잡도를 O(1)로 구현하였다. 리스트의 맨 뒤에 삽입된다.

findMaxIndex함수는 최대 우선순위 항목의 인덱스를 반환하는 함수인데 이를 구현한 이유는 우선순위 큐는 우선순위가 가장 높은 항목을 삭제해야하기 때문에 이를 찾기 위해 위 함수를 구현한 것이다. 이는 탐색 알고리즘과 비슷하게 하나씩 비교해가면서 값이 더 크면 highest를 update해주면서 최대값을 찾아주는 것이다.

다음으로 삭제함수이다. findMaxIndex 함수로 찾아낸 우선순위가 가장 높은 항목을 pop함수로 삭제하는 것이다.

다음으로 peek함수는 삭제함수와 비슷한데 삭제를 시키지 않고 그 값을 반환하는 것이다.

이를 테스트하는 메인함수이다.

q= PriorityQueue()
q.enqueue(34)
q.enqueue(18)
q.enqueue(27)
q.enqueue(45)
q.enqueue(15)
print('PQueue: ',q.items)
while not q.isEmpty():
    print("Max Priority = ",q.dequeue())

결과값

다음과 같이 내림차순 정렬이 됐음을 알 수 있다.

 

우선순위 큐의 시간복잡도는 삽입함수는 append로 인해 시간복잡도가 O(1), 삭제함수의 최대 시간복잡도는 O(n)이다. 최대로 시간 걸릴 경우에는 역정렬되어있을 때이다. 이와 같은 시간 복잡도를 갖는 이유는 MaxFindIndex가 탐색정렬이기 때문이다.