우선순위 큐

 

IndexMinPQ를 Python으로 구현

 

IndexMinPQ의 구성과 주요 기능

이 클래스는 인덱스 기반 최소 우선순위 큐를 구현합니다. 이를 통해 인덱스를 기반으로 효율적으로 원소를 삽입, 삭제, 변경할 수 있습니다.

 

 

 

 

class IndexMinPQ:
    def __init__(self, capacity):
        """
        우선순위 큐를 초기화합니다.
        :param capacity: 큐의 최대 크기
        """
        self.capacity = capacity  # 최대 용량
        self.size = 0  # 현재 큐에 있는 원소의 수
        self.keys = [None] * (capacity + 1)  # 우선순위를 저장하는 리스트 (1부터 시작)
        self.pq = [None] * (capacity + 1)  # 이진 힙의 인덱스를 저장하는 리스트 (1부터 시작)
        self.qp = [-1] * (capacity + 1)  # 특정 인덱스의 위치를 저장하는 리스트 (초기값 -1: 비어있음)

    def is_empty(self):
        """큐가 비어있는지 확인합니다."""
        return self.size == 0

    def contains(self, i):
        """인덱스 i가 큐에 있는지 확인합니다."""
        assert 0 <= i < self.capacity, "인덱스가 범위를 벗어났습니다."
        return self.qp[i] != -1

    def insert(self, i, key):
        """
        새로운 원소를 큐에 삽입합니다.
        :param i: 삽입할 인덱스
        :param key: 삽입할 우선순위 키
        """
        assert 0 <= i < self.capacity, "인덱스가 범위를 벗어났습니다."
        assert not self.contains(i), "이미 존재하는 인덱스입니다."

        self.size += 1  # 큐 크기 증가
        self.qp[i] = self.size  # qp에 새 원소의 위치 저장
        self.pq[self.size] = i  # pq에 인덱스 추가
        self.keys[i] = key  # 키 저장
        self.swim(self.size)  # 힙의 규칙에 맞게 위치 조정

    def min_index(self):
        """최소 키를 가진 인덱스를 반환합니다."""
        assert self.size > 0, "큐가 비어있습니다."
        return self.pq[1]

    def min_key(self):
        """최소 키를 반환합니다."""
        assert self.size > 0, "큐가 비어있습니다."
        return self.keys[self.pq[1]]

    def del_min(self):
        """최소 키를 가진 원소를 삭제하고 해당 인덱스를 반환합니다."""
        assert self.size > 0, "큐가 비어있습니다."

        min_index = self.pq[1]  # 루트 노드(최소 키의 인덱스)
        self.exch(1, self.size)  # 루트와 마지막 노드를 교환
        self.size -= 1  # 큐 크기 감소
        self.sink(1)  # 힙 규칙 복구

        self.qp[min_index] = -1  # 삭제된 인덱스의 qp 값 초기화
        self.keys[min_index] = None  # 삭제된 키 초기화
        self.pq[self.size + 1] = None  # 힙의 마지막 위치 초기화

        return min_index

    def change_key(self, i, key):
        """
        특정 인덱스의 키를 변경합니다.
        :param i: 변경할 인덱스
        :param key: 새로운 키 값
        """
        assert 0 <= i < self.capacity, "인덱스가 범위를 벗어났습니다."
        assert self.contains(i), "존재하지 않는 인덱스입니다."

        self.keys[i] = key  # 새로운 키 값 저장
        self.swim(self.qp[i])  # 힙 규칙 복구
        self.sink(self.qp[i])

    def decrease_key(self, i, key):
        """
        특정 인덱스의 키를 감소시킵니다.
        :param i: 변경할 인덱스
        :param key: 새로운 키 값 (기존 키보다 작아야 함)
        """
        assert 0 <= i < self.capacity, "인덱스가 범위를 벗어났습니다."
        assert self.contains(i), "존재하지 않는 인덱스입니다."
        assert key < self.keys[i], "새로운 키는 기존 키보다 작아야 합니다."

        self.keys[i] = key
        self.swim(self.qp[i])

    def increase_key(self, i, key):
        """
        특정 인덱스의 키를 증가시킵니다.
        :param i: 변경할 인덱스
        :param key: 새로운 키 값 (기존 키보다 커야 함)
        """
        assert 0 <= i < self.capacity, "인덱스가 범위를 벗어났습니다."
        assert self.contains(i), "존재하지 않는 인덱스입니다."
        assert key > self.keys[i], "새로운 키는 기존 키보다 커야 합니다."

        self.keys[i] = key
        self.sink(self.qp[i])

    def delete(self, i):
        """
        특정 인덱스를 큐에서 삭제합니다.
        :param i: 삭제할 인덱스
        """
        assert 0 <= i < self.capacity, "인덱스가 범위를 벗어났습니다."
        assert self.contains(i), "존재하지 않는 인덱스입니다."

        index = self.qp[i]  # 힙에서의 위치
        self.exch(index, self.size)  # 해당 원소와 마지막 원소를 교환
        self.size -= 1  # 큐 크기 감소
        self.swim(index)  # 힙 규칙 복구
        self.sink(index)

        self.keys[i] = None  # 삭제된 키 초기화
        self.qp[i] = -1  # 삭제된 인덱스 초기화

    def greater(self, i, j):
        """i번째 원소가 j번째 원소보다 큰지 확인합니다."""
        return self.keys[self.pq[i]] > self.keys[self.pq[j]]

    def exch(self, i, j):
        """i와 j 위치의 원소를 교환합니다."""
        self.pq[i], self.pq[j] = self.pq[j], self.pq[i]  # 힙 배열에서 교환
        self.qp[self.pq[i]] = i  # qp 업데이트
        self.qp[self.pq[j]] = j

    def swim(self, k):
        """
        힙 규칙을 복구하기 위해 k번째 원소를 위로 올립니다.
        """
        while k > 1 and self.greater(k // 2, k):  # 부모보다 작으면 교환
            self.exch(k, k // 2)
            k = k // 2

    def sink(self, k):
        """
        힙 규칙을 복구하기 위해 k번째 원소를 아래로 내립니다.
        """
        while 2 * k <= self.size:
            j = 2 * k
            if j < self.size and self.greater(j, j + 1):
                j += 1  # 오른쪽 자식이 더 작으면 오른쪽 선택
            if not self.greater(k, j):
                break  # 자식보다 작으면 중지
            self.exch(k, j)
            k = j

 

 

# 사용 예시
if __name__ == "__main__":
    pq = IndexMinPQ(10)

    # 예제 데이터 삽입
    data = [(3.5, 3), (8.3, 1), (1.5, 1), (1.6, 3), (0.5, 8), (0.1, 5)]
    for key, index in data:
        if not pq.contains(index):
            pq.insert(index, key)
        else:
            pq.change_key(index, key)

    # 최소 키 순으로 출력 및 삭제
    while not pq.is_empty():
        print(f"Min Key: {pq.min_key()}, Min Index: {pq.min_index()}")
        pq.del_min()