[Python] 우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐와 힙

우선순위 큐(Priority Queue)

일반 큐와는 다르게 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 구조입니다.
우선순위 큐는 힙(Heap)이라는 자료구조를 활용해 구현 할 수 있으므로 힙을 먼저 알 수 구현할 수 있어야 합니다.

 

힙(Heap)

힙은 위와 같이 완전 이진 트리로 구성되며, 부모 노드는 최대 두개의 자식 노드를 가지고 있습니다.
부모 노드의 인덱스를 i라고 했을 때,
왼쪽 자식 노드는 2i+1, 오른쪽 자식 노드는 2i+2 의 인덱스를 가집니다.

• 최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

heapq 모듈을 사용하여 최소 힙 구현

import heapq

test = [3, 2, 5, 1, 7, 8, 2]

heapq.heapify(test)            # heapify(list) : list를 힙 정렬합니다.
print(test)                    # [1, 2, 2, 3, 7, 8, 5]

heapq.heappop(test)            # 힙에서 가장 작은 요소(최소힙이므로 루트 노드)를 반환합니다.
print(test)                    # [2, 2, 5, 3, 7, 8]

heapq.heappush(test, 4)     # 힙에 항목을 삽입합니다. > heappush(list, 값)
print(test)                    # [2, 2, 4, 3, 7, 8, 5]

heapq 모듈을 사용하여 최대 힙 구현

test = [3, 2, 5, 1, 7, 8, 2]
heap = []

for i in test:                            # heap에 (-값, 값) 튜플 형태로 삽입
    heapq.heappush(heap, (-i, i))

# 최대 힙 출력
for h in heap:
    print(h[1], end = " ")                # 8 5 7 1 2 3 2

# heappop
heapq.heappop(heap)[1]                    # [1]인덱싱을 통해 값 접근
                                        # 루트 노드인 8 반환

힙 정렬 리스트에 (-i, i) 형태로 삽입하게 되면 튜플의 첫번째 요소를 우선순위로 최소 힙 정렬을 구성합니다.
실제 값은 두번째 요소에 저장되있으므로 heapq.heappop(heap)[1] 하면 루트 노드가 반환되고
실제 값을 확인할 수 있습니다.

 

• heapq.heappushpop(heap, item)
  힙을 유지하면서 힙에 item을 push한 다음, 힙에서 가장 작은 항목을 pop하고 반환합니다.
  push한 다음 pop을 호출하는 것보다 효율적입니다.
• heapq.heapreplace(heap, item)
  힙에서 가장 작은 항목을 pop하고 반환하며, 새로운 item을 push합니다.
  동일하게 push한 후 pop하는 것보다 효율적이긴하나, push되는 값보다 pop되는 값이 더 클 수 있습니다.
• heapq.merge(*iterables, key=None, reverse=False)
  여러 정렬된 시퀀스를 단일 정렬된 시퀀스로 병항하여 반환합니다.

 

리스트를 이용한 최대힙 구현

class Heapify(obejct):
    def __init__(self, data = None):
        self.data = [] or data            # data가 None이면 빈 리스트[]

        # 힙 정렬은 절반의 노드만 heapify 수행하면 됩니다.
       for i in range(len(data) // 2, -1, -1):
           self.__max_heapify__(i)                # __max_heapify__() : 최대힙으로 heapify 수행

    def __repr__(self):
        return repr(self.data)

    def left_child(self, i):
        return (2 * i) + 1                    # 왼쪽 자식 노드 인덱스

    def right_child(self, i):
        return (2 * i) + 2                    # 오른쪽 자식 노드 인덱스

    def parent(self, i):
        return (i - 1) // 2                    # 자식노드는 2*i+1, 2*i+2 이므로 i의 인덱스 구해서 반환

    def __max_heapify__(self, i):
        largest = i                    # largest 임시 변수, 부모 노드의 인덱스
        left = self.left_child(i)
        right = self.right_child(i)
        n = len(self.data)

        # 만약 left가 리스트 범위 내이고, left가 존재하며 left의 값이 largest값 보다 큰 경우
        if left < n and self.data[left] > self.data[largest] and left:
            largest = left

        # 오른쪽 자식도 존재할 수 있으므로 왼쪽 비교 후 항상 오른쪽도 비교해주어야 함
        if right < n and self.data[right] > self.data[largest] and right:
            largest = right

        # 자식노드와 비교 후 largest값에 변경이 이루어졌을 경우
        # (largest가 자식노드 인덱스로 변경되었을 경우) > 인덱스를 맞춰줬으니 인덱스로 값을 바꿔줄 차례
        if i != largest:
            self.data[i], self.data[largest] = self.data[largest], self.data[i]
            self.__max_heapify__(largest)            # largest기준으로 heapify 추가 수행

        # 최대값 반환하기
        def extract_max(self):
            n = len(self.data)
            max_element = self.data[0]            # 루트 노드를 반환할 변수에 대입
            self.data[0] = self.data[n-1]        # 가장 마지막 노드를 루트노드 자리로 이동
            self.data = self.data[:n-1]            # 마지막 노드를 루트로 복사했으므로 리스트 슬라이싱
            self.__max_heapify__(0)                # 루트 노드부터 heapify 수행

            return max_element

        # 최대힙 리스트에 삽입    
        def insert(self, item):
            self.data.append(item)
            i = len(self.data) - 1

            # i가 0(루트 인덱스)가 아니고 부모 노드보다 i노드의 값이 클때까지 반복
            while i != 0 and item > self.data[self.parent(i)]:
                self.data[i] = self.data[self.parent(i)]    # i의 값이 부모 노드 값보다 크기때문에
                                                            # 부모 노드의 값을 i노드에 대입
                i = self.parent(i)            # 인덱스를 부모 인덱스로 저장(부모 노드로 올라가면서 검사 반복)

            self.data[i] = item

# 확인
if __name__ == "__main__"
     list1 = [3, 2, 5, 1, 7, 8, 2]
     heap = Heapify(list1)
     print(heap)                # [8, 7, 5, 1, 2, 3, 2]

     heap.extract_max()            # 8 반환
     print(heap)                # [7, 2, 5, 1, 2, 3]

     heap.insert(10)
     print(heap)                # [10, 2, 7, 1, 2, 3, 5]

 

heapq모듈을 사용해서 우선순위 큐 구현

import heapq

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

    def push(self, priority, item):        # 우선순위와 값 매개변수
        heapq.heappush(self.queue, (-priority, self.index, item))
        # (-우선순위, 인덱스, 값) 형태로 heappush를 하면 우선순위가 높을수록 앞에 배치됩니다.

        self.index += 1

    def pop(self):
        return heapq.heappop(self.queue)[-1]        # heappop을 수행한 후 [-1]인덱싱을 통해 값에 접근합니다.

    def __repr__(self):
        return repr(self.queue)

if __name__ == "__main__":
    q = PriorityQueue()
    q.push(20, "Low")
    q.push(0, "Very Low")
    q.push(50, "Middle")
    q.push(100, "Very High")
    1. push(70, "High")

    print(q)
    # 결과
    # [(-100, 3, 'Very High'), (-70, 4, 'High'), (-20, 0, 'Low'), (0, 1, 'Very Low'), (-50, 2, 'Middle')]

    q.pop()        # (-100, 3, 'Very High') 반환
    q.pop()        # (-70, 4, 'High') 반환
    q.pop()        # (-50, 2, 'Middle')

    print(q)    # [(-20, 0, 'Low'), (0, 1, 'Very Low')]

이상으로 힙, 힙을 이용한 우선순위 큐를 공부해 보았습니다.
다음으로는 노드를 이용해서 연결리스트를 해볼게요!