[데이터구조] 재귀호출 응용 및 힙

우선순위 큐

우선순위 큐 : 원소를 제거할 시, 가장 우선순위가 높은 원소를 제거 (아래의 예시에서는 5부터 제거되었지만 실제 코드에서는 작은 값이 우선순위가 높다고 가정되어서 작은 값부터 제거됩니다.)

우선순위 큐 : 배열로 구현하기

class priorityQueue:
    '''
    우선순위 큐를 리스트으로 구현합니다
    '''

    def __init__(self) :
        self.data = [0]

    def push(self, value) :
        '''
        우선순위 큐에 value를 삽입합니다.
        '''
        self.data.append(value)


    def top(self) :
        '''
        우선순위가 가장 높은 원소를 반환합니다. 만약 우선순위 큐가 비어있다면 -1을 반환합니다.
        '''

        if len(self.data) == 1: 
            return -1 
        else:
            return min(self.data[1:])

    def pop(self) :
        '''
        우선순위가 가장 높은 원소를 제거합니다.
        '''
        if self.top() != -1: 
            index = self.data.index(self.top())
            del self.data[index]

def main():
    myPQ = priorityQueue()

    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

    myPQ.push(1)
    myPQ.push(4)
    myPQ.push(3)
    myPQ.push(2)

    print(myPQ.top())
    myPQ.pop()

    print(myPQ.top())
    myPQ.pop()

if __name__ == "__main__":
    main()

우선순위 큐 : 이진 트리를 이용해서 구현하기 (힙)

힙 : 부모의 값이 항상 자식보다 작은 완전 이진 트리

• 부모의 값이 항상 자식보다 우선순위가 높음
• 완전 이진 트리 : 트리에 삽입을 할때, 자식의 개수가 2개씩 꽉꽉 채우도록 삽입되는 형태 (아래의 그림에서 값이 삽입되면 7의 자식노드로 들어가야함)

힙에서 값을 삽입하는 경우

• 힙에 값을 삽입하는 경우 완전 이진트리를 맞추도록 값을 삽입해야 합니다.
• 삽입 후 부모노드와 자식노드간의 우선순위관계가 맞는지 확인해주는 작업이 필요합니다.
• 시간복잡도 : O(logn) - 트리의 높이가 높으면 시간복잡도가 높음 (트리의 원소 개수는 2^n-1이고 이때 n이 높이가 됨)

마찬가지로 그 뒤에 27이라는 값을 삽입하는 경우 아래와 같은 과정을 거치게 됩니다.

한번 이번에는 힙에서 값을 삭제하는 경우에 대해서 살펴보도록 하겠습니다.

• 삭제의 경우 가장 우선순위가 높은 부모노드부터 삭제가 됩니다.
• 이후, 가장 마지막 자식노드를 부모노드에 넣습니다.
• 그리고 자연스럽게 우선순위가 높은 노드가 부모노드로 오도록 조정해주면 삭제가 완료됩니다.
• 시간복잡도 - 트리의 높이가 높으면 시간복잡도가 높음 (트리의 원소 개수는 2^n-1이고 이때 n이 높이가 됨)

우선순위가 가장 높은 부모노드 삭제

마지막 자식노드를 부모노드에 삽입

우선순위가 맞도록 노드의 순서를 조정. 이때 23이 3쪽으로 내려가는 이유는 3의 우선순위가 4보다 더 높기때문입니다.

마찬가지로 이후 하나의 값을 더 제거하는 과정까지 살펴보면 아래와 같습니다.

우선순위 큐는 참고로 정렬에도 활용할 수 있습니다. 우선순위 큐의 pop()에서는 우선순위가 높은 것부터 나오니, 모든 값을 push하고 pop 해주면 정렬된 순서로 나오게 됩니다.

우선순위 큐 구현하기 (힙)

class priorityQueue:
    '''
    우선순위 큐를 힙으로 구현합니다
    '''

    def __init__(self) :
        self.data = [0]

    def push(self, value) :
        '''
        우선순위 큐에 value를 삽입합니다.
        '''
        self.data.append(value)

        index = len(self.data) - 1

        while index != 1:
            if self.data[index//2] > self.data[index]:
                temp = self.data[index]
                self.data[index] = self.data[index//2]
                self.data[index//2] = temp

                index = index//2
            else:
                break


    def top(self) :
        '''
        우선순위가 가장 높은 원소를 반환합니다. 만약 우선순위 큐가 비어있다면 -1을 반환합니다.
        '''
        if len(self.data) == 1:
            return -1
        else :
            return self.data[1]


    def pop(self) :
        '''
        우선순위가 가장 높은 원소를 제거합니다.
        '''
        if len(self.data) == 1:
            return

        self.data[1] = self.data[-1]
        self.data.pop()

        index = 1

        while True:
            priority = -1

            # 1 아무 자식도 없는 경우
            if len(self.data)-1 < index * 2:
                break
            # 2 오직 왼쪽 자식만 있는 경우
            elif len(self.data) - 1 < index * 2 + 1:
                priority = index * 2
            else:
                if self.data[index*2] < self.data[index*2+1]:
                    priority = index * 2
                else:
                    priority = index * 2 +1

            if self.data[index] > self.data[priority]:
                temp = self.data[index]
                self.data[index] = self.data[priority]
                self.data[priority] = temp

                index = priority
            else:
                break


def main():
    myPQ = priorityQueue()

    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

    myPQ.push(1)
    myPQ.push(4)
    myPQ.push(3)
    myPQ.push(2)

    print(myPQ.top())
    myPQ.pop()

    print(myPQ.top())
    myPQ.pop()

if __name__ == "__main__":
    main()

우선순위 큐 구현하기 (내장힙)

from heapq import heappush, heappop

class priorityQueue:
    '''
    우선순위 큐를 힙으로 구현합니다
    '''

    def __init__(self) :
        self.data = []

    def push(self, value) :
        '''
        우선순위 큐에 value를 삽입합니다.
        '''
        heappush(self.data, value)

    def top(self) :
        '''
        우선순위가 가장 높은 원소를 반환합니다. 
        만약 우선순위 큐가 비어있다면 -1을 반환합니다.
        '''
        if len(self.data) <= 0 :
            return -1
        else :
            return self.data[0]


    def pop(self) :
        '''
        우선순위가 가장 높은 원소를 제거합니다.
        '''
        if len(self.data) <= 0 :
            return
        else :
            heappop(self.data)


def main():
    myPQ = priorityQueue()

    '''
    테스트를 하고싶으면, 아래 부분을 수정합니다.
    '''

    myPQ.push(1)
    myPQ.push(4)
    myPQ.push(3)
    myPQ.push(2)

    print(myPQ.top())
    myPQ.pop()

    print(myPQ.top())
    myPQ.pop()

if __name__ == "__main__":
    main()

출처

• Elice Academy | 데이터구조 - 재귀호출 응용 및 힙