우선순위 큐 ( Priority Queue )

우선순위 큐 ( Priority Queue )

보통 큐는 배열이나 연결 리스트 등으로 구현하는 것이 일반적이다. 그러나, 그렇게 구현하게 된다면, 다음과 같은 문제가 발생하게 된다.

1. 배열
   • 데이터 삽입 / 삭제의 경우 데이터를 한칸씩 앞으로 밀거나 당겨야 하는 연산 생겨 시간 복잡도가 증가하게 된다.
2. 연결 리스트
   • 검색 할 때 처음부터 끝까지 훑으면서 찾아봐야 하는 문제가 생긴다.

따라서 우리는 우선순위 큐를 만들 때 힙 ( Heap ) 자료구조를 사용하여 개발한다.

Heap

힙 이란 다음과 같다.

• 완전 이진 트리의 한 종류
• 여러 값중에 최대값이나 최솟값을 찾아내도록 만들어진 자료구조
• 반 정렬상태 ( 느슨한 정렬 상태 ) 를 유지.
  • 느슨한 정렬 상태 : 위에서 부터 딱딱 큰것 ~ 작은것 순으로 내려오는게 아닌, 부모가 자식보다 크거나 작은 것을 보장하는 상태

또한 힙 트리에서는 중복된 값을 허용하는데, 이진 탐색 트리에서는 중복된 값을 허용하지 않는다는 점이 다르다.

 

Min - Max Heap

힙에는 최대 힙( Max heap ) / 최소 힙( Min heap ) 2가지가 있는데, 각각 키 값이 부모의 값 이상이거나 이하인 힙이라고 정의 할 수 있다.

 

힙은 평범하게 배열로 되며, 배열의 첫 인덱스인 0 은 사용하지 않고 구현한다고 한다. 힙에서 부모 노드와 자식 노드의 관계는 다음과 같다.

• 왼쪽 자식의 인덱스 = ( 부모의 인덱스 ) * 2
• 오른쪽 자식의 인덱스 = ( 부모의 인덱스 ) * 2 + 1
• 부모의 인덱스 = ( 자식의 인덱스 ) / 2

 

자료구조에서의 삽입 / 삭제 방식

삽입과 삭제는 각각 O( log n ) 의 시간 복잡도를 가진다.

- 삽입은 다음처럼 구현한다.

1. 새로운 노드를 힙의 마지막 노드에 삽입. ( 배열의 끝 )
2. 새로운 노드를 계속하여 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

- 삭제는 다음처럼 구현한다.

1. 최댓값을 삭제하는 경우 루트 노드를 삭제한다. ( Max heap 의 경우 )
2. 삭제된 루트 노드에 마지막 노드를 가져온다. ( 배열의 마지막을 첫번째에 삽입 )
3. 계속하여 교환하여 힙의 성질을 만족시킨다.

코드로의 구현

code로 보면서 더 잘 이해할 수 있을 것이다. 편의를 위해서 부모 - 오른쪽 자식 - 왼쪽 자식 순으로 크게 잡았다. ( Max Heap 이기 때문 )

class MaxHeap():
    ROOT = 0

    def __init__(self, initValue=[]):
        self.value = []
        if len(initValue) != 0:
            for i in initValue:
                self.addValue(i)

    def addValue(self, v):
        '''
            v : value for add.
        '''
        self.value.append(v)
        index = len(self.value) - 1
        ret = self.calcParentValue(index)
        
        while ret:
            index = self.getParentIndex(index)
            ret = self.calcParentValue(index)
    
    def calcParentValue(self, index):
        pIndex = self.getParentIndex(index)
        # Compare with parents and if parents is not big as child, change it.
        if self.value[pIndex] < self.value[index]:
            temp = self.value[index]
            self.value[index] = self.value[pIndex]
            self.value[pIndex] = temp
            return True
        else:
            return False

    def removeValue(self):
        popValue = self.value[self.ROOT]
        self.value[self.ROOT] = self.value[-1]
        del self.value[-1]

        index = self.ROOT
        if self.getLargerChild(index):
            ret = self.calcLeftChildValue(index)
            index = self.getLeftChildIndex(index)
        else:
            ret = self.calcRightChildValue(index)
            index = self.getRightChildIndex(index)
        
        while ret:
            if self.getLargerChild(index):
                ret = self.calcLeftChildValue(index)
                index = self.getLeftChildIndex(index)
            else:
                ret = self.calcRightChildValue(index)
                index = self.getRightChildIndex(index)
        return popValue

    def calcLeftChildValue(self, index):
        # Compare with left child value and if parents is not big as child, change it.
        lcIndex = self.getLeftChildIndex(index)
        if lcIndex >= len(self.value):
            return False
        elif self.value[lcIndex] > self.value[index]:
            temp = self.value[index]
            self.value[index] = self.value[lcIndex]
            self.value[lcIndex] = temp
            return True
        else:
            return False

    def calcRightChildValue(self, index):
        # Compare with right child value and if parents is not big as child, change it.
        rcIndex = self.getRightChildIndex(index)
        if rcIndex >= len(self.value):
            return False
        elif self.value[rcIndex] > self.value[index]:
            temp = self.value[index]
            self.value[index] = self.value[rcIndex]
            self.value[rcIndex] = temp
            return True
        else:
            return False

    def getLargerChild(self, index):
        # If left is larger, return True, else False
        if self.getRightChildIndex(index) >= len(self.value):
            return True
        else:
            return self.value[self.getLeftChildIndex(index)] > self.value[self.getRightChildIndex(index)]

    def getParentIndex(self, index):
        if index == self.ROOT:
            return self.ROOT
        elif index % 2 == 0:
            return int(index / 2) - 1
        else:
            return int(index / 2)

    def getLeftChildIndex(self, index):
        return (index + 1) * 2 - 1
    
    def getRightChildIndex(self, index):
        return (index + 1) * 2
    
    def printHeap(self):
        '''
        for i in range(0, len(self.value)):
            print("Heap value [" + str(i) + "] is " + str(self.value[i]))
        '''
        print(self.value)

heap = MaxHeap([7, 5, 10, 20, 10, 23, 17, 20])
heap.printHeap()
print(heap.removeValue())
heap.printHeap()

 

Python 에서의 기본 라이브러리

파이썬은 기본적으로 heap 을 heapq 라이브러리로 구현하여 다음처럼 쓸 수 있게 해 두었다.

import heapq

heap = []

# Min-Heap만 지원
heapq.heappush(heap, 4)
a = heapq.heappop(heap)
b = heap[0] # 최솟값 삭제하지 않고 찾기

heap = [2, 5, 1, 20, 3, 17]
heapq.heapify(heap) # 기존 배열을 Heap 으로 변환

# Max-Heap
heap = []
nums = [4, 1, 7, 3, 8, 5]

for n in nums:
	heapq.heappush(heap, (-n, n)) # ( 우선순위, 값 )
# Min-Heap을 사용해서 Max-Heap 구현

 

 

 

 

 

참조

Notion Blog ( 본인 )

Notion – The all-in-one workspace for your notes, tasks, wikis, and databases.

그 외 자료구조 블로그1, 블로그2, 블로그3