우선순위 큐와 힙의 차이를 알아보자.

이번 포스팅에는 스택, 큐, 힙 알고리즘 문제를 풀어본 궁금증으로 비슷한듯 다른 우선순위큐와 힙의 차이에 포스팅해보려고 한다.

먼저 결론적인 개념은 다음과 같다.

큐(Queue) : 먼저 들어오는 데이터가 먼저 나오는 선입선출(FIFO) 구조
우선순위 큐(Priority Queue) : 우선순위가 높은 데이터가 먼저 나가는 구조
힙(Heap) : 루트 노드에 최대값이나 최소값을 저장하고 있는 완전이진트리

Queue

큐 자료구조 관련 문제 : 트럭

관련 문제로 [백준]트럭↗ 문제와 [프로그래머스]다리를 지나는 트럭↗ 문제가 있다.

트럭 문제는 트럭들의 최대하중을 기준으로 최대 하중보다 크면 다리 큐(Queue)에 0을 추가(Push)하고 적으면 다음 트럭을 추가하는 문제이다.

Push : 다리 하중을 버틸 수 있으면 다음 트럭 추가, 그렇지 못하면 0 추가
Pop : 다리에 트럭들의 수와 다리의 길이(w)가 같으면 트럭 하나를 빼낸다.

이렇듯, 트럭 문제는 먼저 들어간 차량이 먼저 나가는 형식으로 문제를 풀면 된다.

📌 원형 큐
스택이나 큐를 이용하면 다양한 프로그램을 만들 수 있다. 그 중에서 원형 큐는 원형으로 이루어진 큐를 말하면 앞에서 데이터를 빼고 해당 데이터가 유효하지 않으면 뒤로 데이터를 보내는 방식이다. 원형 큐를 구현하려면 `deque`를 사용하는게 좋다. 글로 보면 이해가 안될 테니 다음 문제를 보자.

해당 문제↗는 회전 연산에서 최소 값을 출력하는 문제이다.

중간점을 기준으로 왼쪽이 더 빠르면 앞 데이터를 빼서 뒤로 넘긴다. 만약 오른쪽이 더 빠르면 뒤 데이터를 빼 앞으로 넘기면 된다.

왼쪽 방향으로 회전 : popleft() + append()
오른쪽 방향으로 회전 : pop() + appendleft()

우선순위 큐

우선순위 큐(Priority Queue)는 말그대로 우선순위가 높은 데이터가 먼저 빠져나가는 형태의 자료구조이다.

추상적으로 생각한다면, 큐는 일렬로 된 큐에서 우선순위에 따라 정렬하고 뽑아내는 것이고 힙은 값을 꺼낼때마다 정렬되어서 나오도록하는 이진트리 형태일 것이다. 힙에 대한 이야기는 다음에 나올 예정이다.

우선순위 큐의 연산

insert() : 우선순위 큐에 x를 추가한다
remove() : 우선순위 큐에 가장 우선순위가 높은 요소를 삭제하고 반환한다.
find() : 우선순위 큐에서 가장 우선순위가 높은 요소를 반환한다.

Heap

힙(Heap)은 이진 트리를 기반의 형태로, 최대 값과 최소 값을 찾아낼 수 있는 자료구조이다.

힙의 특징

완전이진트리의 형태로 이루어져 있다.
부모노드와 자식노드간의 대소 관계가 성립한다. (부모노드가 자식노드보다 크거나 같다.) 반정렬 상태를 말한다.
힙의 종류로 최대 힙(Max Heap)과 최소 힙(Min Heap)이 존재한다.
힙은 중복값을 허용한다.

이진 탐색 트리(BST)와의 차이로는 둘다 이진 트리이지만 힙은 자식의 좌우 측 노드와 부모노드 간의 값 크기 조건이 없다는 것이다.

힙의 시간복잡도

기본적으로 정렬된 상태의 힙의 자료구조는 O(1)이다. 이런 경우는 루트 노드가 최소값이거나 최대값일 때를 의미한다.

하지만 모든 경우가 그렇지는 않다. 힙에 새로운 값이 들어와 다시 우선순위가 높은 값을 루트노드로 보내기 위해 `heapify` 과정을 거치게되는데 이런 경우에는 O(log n)의 시간 복잡도로 최소값이나 최대값에 접근할 수 있게 된다.

여기서 특별한 점은 일반적은 배열이나 연결리스트의 삽입, 삭제 연산을 하게되면 O(n)의 시간 복잡도가 발생하지만 힙은 트리구조로 되어 있기 때문에 효율적인 작업을 할 수 있다.

힙과 우선순위 큐의 차이?

힙은 자료구조이다. 그리고 우선순위 큐는 추상적인 자료형이다.

결국엔 Heap을 이용해 우선순위 큐를 만들 수 있는 것이다. 물론, 우선순위 큐는 배열이나 연결리스트를 통해서도 만들 수 있지만 Heap이 성능면에서 우월하기 때문이다.

여기서, 추상자료형(Abstract data type, ADT)과 자료구조(Data Structure, DS)의 차이에 대해 설명하자면 추상자료형은 실제로 구현 방법이 명시하고 있지 않고 어떤 동작들인지 개념적인 부분만 설명한 것을 이야기한다. 반면에, 자료구조는 실제로 구현하는 것을 말하며 이를 통해 시간 복잡도도 알 수 있는 것이다.

만약 큐의 특징과 큐의 예시를 설명한 것이라면 ADT 관점에서 이야기한 것이고 이를 실제로 어떤 구현체를 통해 구현했다는 것은 자료구조 관점에서 설명하는 것이다.

힙을 배열로 구현하기

힙은 배열로 구현할 수 있다. 기본적으로 완전이진트리 자체가 비어있는 공간이 없기 때문에 배열로 구현하기에 용이하다.

class Maxheap:
    def __init__(self):
        self.heap = list()
        self.heap.append(None) # 초기 데이터가 들어갈 인덱스를 1부터 시작

    def get_parent(self, index):
        return self.heap[index//2]

    def get_left_child(self, index):
        return self.heap[index*2 + 1]

    def get_right_child(self, index):
        return self.heap[index*2 + 2]

삽입 연산

힙에 삽입하기 위해 힙 구조의 성질을 만족하면서 새로운 값을 추가해야한다.

만약, 부모노드보다 큰 경우 삽입된 자식노드와 교환(Swap)하고 그렇지 않으면 정지한다.

이 과정을 반복하여 정지가 되면 재구조화가 끝난다. (더이상 부모노드와 교환할 필요 없을 때 까지)

    def move_up(self, inserted_i):
        if inserted_i <= 1:
            return False
        
        parent_i = self.get_parent(self, inserted_i)
        if self.heap[inserted_i] > self.heap[parent_i]:
            True
        else:
            False

    def insert(self, data):
        # 데이터 추가
        if len(self.heap) == 0:
            self.heap.append(None)
            self.heap.append(data)
            return self.heap
        self.heap.append(data)

        # 방금 들어온 데이터의 인덱스
        inserted_i = len(self.heap) - 1

        while self.move_up(inserted_i):
            parent_i = self.get_parent(inserted_i)
            self.heap[inserted_i], self.heap[parent_i] = self.heap[parent_i], self.heap[inserted_i] # swap
            inserted_i = parent_i # 인덱스 변경

        return self.heap

삭제 연산

루트 노드가 삭제되면 가장 말단 노드가 루트 노드로 대체되고 재구조화(heapify)과정을 수행한다.

만약, 대체된 말단 노드가 자식 노드보다 작으면 교환(Swap)하고 그렇지 않으면 정지한다.

여기서 좌측과 우측을 검사하면서 재구조화를 진행해야한다. (더이상 자식노드와 교환할 필요 없을 때 까지)

     def move_down(self, parent_i):
        left_child_i = self.get_left_child(parent_i)
        right_child_i = self.get_right_child(parent_i)

        if left_child_i < len(self.heap) and self.heap[left_child_i] > self.heap[parent_i]:
            self.heap[left_child_i], self.heap[parent_i] = self.heap[parent_i], self.heap[left_child_i]
            parent_i = left_child_i
        elif right_child_i < len(self.heap) and self.heap[right_child_i] > self.heap[parent_i]:
            self.heap[right_child_i], self.heap[parent_i] = self.heap[parent_i], self.heap[right_child_i]
            parent_i = right_child_i
        else:
            return False
        return True

        

    def pop(self):
        if len(self.heap) <= 1:
            return None
        
        returned_data = heap.pop()
        self.heap[1] = returned_data
        parent_i  = 1
        while self.move_down(parent_i):
            continue
        return self.heap

힙 정렬

힙 정렬(Heap Sort)는 N개의 데이터를 힙에 넣으면 N개 만큼 삭제하고 정렬을 통해 깨진 힙을 재구조화를 통해 반복하는 알고리즘을 말한다. 힙정렬은 퀵 정렬이 O(N^2)라고 가정했을 때 O(logN)이기 때문에 효율적인 알고리즘이다.

힙 관련 문제 풀어보기

파이썬에서는 `heapq` 라이브러리를 사용하면 우선순위 큐를 쉽게 구현할 수 있다.

heappush(heap, item) : 힙에 item 값 넣기
heappop(heap) : 힙에 가장 작은 항목 반환하기, 만약 힙이 비어 있는 경우 IndexError 발생
heappushpop(heap, item) : 힙에 item 값을 넣은 다음, 힙에 가장 작은 항목을 추출한다.
heapify(list) : 리스트를 선형시간으로 제자리에서 힙으로 변환한다.

해당 문제는 [백준] 소수의 곱↗이다.

소수의 갯수와 N번째, 그리고 그 소수들의 배열이 주어지면 소수의 곱을 통해 N번째 데이터를 출력하면 된다.

N번째까지 반복문을 돌리기에 최대 100,000번 까지 반복해도 되기 때문에 문제 없다.

`2, 3, 5, 7` 이라는 힙을 만들어 4가지의 소수를 곱한 후 다시 힙에 넣는 아이디어를 생각해볼 수 있겠다.

그렇다면 19번의 반복을 돌리면서 턴마다 최소값을 추출해 다시 2,3,5,7를 곱해 넣으면 19번째 되었을 때 우리가 원하는 답을 찾을 수 있게된다.

힙과 관련된 문제
[백준] 이중 우선순위 큐 : 두개의 우선순위 큐를 만들어 데이터를 뺄 때 이미지 삭제된 데이터인지 인덱스를 통해 확인하면 된다.
[프로그래머스] 스코빌지수 : 소코빌 지수가 K 이상이 되었을 때 최소 스코빌 지수 두개를 빼내 반복해서 계산하면 되는 문제이다.

☕️ 포스팅이 도움이 되었던 자료

오늘도 저의 포스트를 읽어주셔서 감사합니다.

설명이 부족하거나 이해하기 어렵거나 잘못된 부분이 있으면 부담없이 댓글로 남겨주시면 감사하겠습니다.

'Algorithm Study' 카테고리의 다른 글

트리 순회 알고리즘 (0)	2024.03.14
[코테스터디] 정렬 (0)	2024.03.11
[코테스터디] 이진 탐색 (0)	2024.01.08
[코테스터디] 다이나믹 프로그래밍(DP) (0)	2024.01.04
[코테스터디] 그리디(Greedy) (0)	2024.01.03