우선순위 큐는 데이터의 우선순위에 따라 접근할 수 있는 자료구조입니다. 이번에는 배열을 이용하여 우선순위 큐를 구현하는 방법에 대해 알아보겠습니다.

구현 방법

1. 배열을 사용하여 우선순위 큐를 구현합니다.
2. 각 요소의 우선순위를 기준으로 정렬된 배열을 유지합니다.
3. 새로운 요소를 삽입할 때, 배열의 적절한 위치에 삽입하여 정렬된 상태를 유지합니다.
4. 가장 우선순위가 높은 요소를 삭제할 때, 배열의 첫 번째 요소를 삭제하고 반환합니다.

예시 코드

다음은 배열을 이용한 우선순위 큐의 예시 코드입니다. 이 예시 코드는 Python 언어로 작성되었습니다.

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def is_empty(self):
        return len(self.queue) == 0

    def insert(self, item):
        self.queue.append(item)  # 요소를 끝에 추가
        self.queue.sort(reverse=True)  # 우선순위에 따라 정렬

    def delete(self):
        if self.is_empty():
            return "Priority queue is empty"

        return self.queue.pop(0)  # 가장 앞의 요소를 삭제하고 반환

# 우선순위 큐 테스트
pq = PriorityQueue()
pq.insert(5)
pq.insert(2)
pq.insert(8)
print(pq.delete())  # 8 출력
print(pq.delete())  # 5 출력

위의 코드에서 PriorityQueue 클래스는 배열을 사용하여 우선순위 큐를 구현합니다. insert 메서드는 새로운 요소를 삽입하고, delete 메서드는 가장 우선순위가 높은 요소를 삭제하고 반환합니다.

요약

이렇게 배열을 이용하여 우선순위 큐를 구현할 수 있습니다. 배열을 사용하면 삽입과 삭제 연산의 시간 복잡도는 O(nlogn)으로 비효율적이지만, 간단하고 쉽게 구현할 수 있습니다.

#TechBlog #PriorityQueue