[자료구조] Heap과 Priority Queue란? / 활용 및 예제 (백준 11279)

Heap이란?

힙은 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리의 일종입니다.

완전이진트리란, 왼쪽부터 차례로 마지막 레벨의 노드를 제외한 모든 노드가 채워져있는 트리입니다.

최솟값이나 최댓값을 찾기 위해 배열은 O(n)의 시간이 걸리는 반면, 힙은 O(log2n)의 시간이 걸리기에 효율적입니다.

힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 고안되었습니다.

 

힙의 형태는 다음과 같습니다.

 

1. 왼쪽부터 채워진 완전 이진 트리이며

2.  자식보다 부모 노드의 값이 큰 최대힙과 자식보다 부모노드의 값이 작은 최소힙이 있다.

 

탐색을 위한 이진탐색트리(BST)와 다르게, 힙은 최솟값과 최댓값을 찾기 위함입니다.

이때 두 자료구조의 차이점은 BST는 왼쪽 자식 노드 - 부모 노드 - 오른쪽 자식 노드의 순서로 값이 커져야 하는 반면

힙은 그것과 관계없이 부모 노드가 자식 노드보다 작거나 커야합니다.

또한 이진탐색트리는 중복을 허용하지 않지만 힙은 중복을 허용합니다.

 

힙은 배열을 통해 구현할 수 있는데, 배열의 0번째 인덱스(루트 노드 인덱스)를 제외한 상태에서

노드 인덱스를 n이라 할 때 아래와 같이 구현합니다.

 

- left-child index : 2n

- right-child index : 2n + 1

- parent index : n / 2

 

이같은 heap 자료구조를 통해 우선순위 큐를 구현할 수 있습니다.

 

Priority Queue란?

우선순위 큐란 힙의 자료구조로 만든, 들어가는 순서와 관계없이 큐에서 삭제(출력)될 때 우선순위에 맞게 삭제되는 추상적인 자료형입니다. 이때 우선순위는 최소힙이면 낮은 값, 최대힙이면 높은 값 순서라 생각해도 됩니다.

그렇기에 큐는 선형 자료구조인 반면, 우선순위 큐는 들어간 순서에 관계없이 데이터가 나오는 비선형 자료형입니다.

 

이러한 우선순위 큐는 os 잡 스케줄링이나 네트워크 트래픽 제어에 활용할 수 있습니다.

 

Priority Queue의 연산?

우선순위 큐(힙)의 삽입은 완전이진트리를 만족하는 형태에서 제일 낮은 레벨의 노드에 삽입된 후,

부모 노드와 대소 비교를 통해 최대 루트 노드까지 거슬러 올라가며 최대힙을 재구성합니다.

이 과정의 시간복잡도는 완전이진트리인 힙의 높이만큼 걸리기에 O(log2n)이 됩니다.

 

삭제는 루트 노드(우선순위가 가장 높은) 원소를 삭제한 뒤, 가장 마지막 원소를 루트 노드의 위치로 옮깁니다.

그 뒤 루트 노드의 자식 노드와 대소비교를 통해 마지막 원소가 루트에서 내려갑니다.

이 과정도 삽입과 마찬가지로 O(log2n)이 걸리게 됩니다.

 

 Heap(Priority Queue) 예제

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

해당 문제는 최대힙의 삽입과 삭제를 구현하는 문제입니다.

heapq 라이브러리를 통해 힙을 만든 뒤 인풋 값이 0일 때 heappop을 실행함으로써 해결할 수 있었습니다.

주의할 점은 heapq 라이브러리는 최소힙을 생성하기 때문에 heappush의 파라미터로 마이너스 연산을 수행함으로써 최대힙의 역할을 수행할 수 있게 했습니다.

import heapq
import sys

n = int(sys.stdin.readline())
heap = []
for i in range(n):
    x = int(sys.stdin.readline())
    if x != 0:
        heapq.heappush(heap, -x) #heapq는 minheap, -연산을 통해 최대힙으로 사용
    else:
        if len(heap) == 0:
            print(0)
        else:
            print(abs(heapq.heappop(heap)))