[자료구조] 힙과 우선순위 큐(heap&priority queue)

이번 포스트에서는 힙과 우선순위 큐에 대하여 알아본다.

<C++로 쉽게 풀어쓴 자료구조>에서 많은 부분을 참고하여 정리했다.

 

우선순위 큐란 무엇일까?

우선 큐는 선입선출의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가는 자료구조라는 사실은 알고 있다.

그렇지만 세상에는 우선순위에 따라 순서를 변경해야 하는 문제들이 있다.

소프트웨어를 예로 들어보자. 내가 핸드폰으로 1시간짜리 플레이리스트를 듣고 있었는데, 도중에 친구에게 전화가 온다. 이때 음악이 끝나지 않았다고 해서 단순하게 순서대로 일을 처리한다면 우리는 전화를 받지 못할 것이다.

따라서 각각의 프로세스에 우선순위를 부여하여 더 중요한 프로세스가 먼저 처리되도록 해야 한다. 이때 우선순위 큐를 사용하는 것이다.

 

 

우선순위 큐를 구현하는 방법으로는 배열을 이용하거나 연결리스트를 사용하는 방법도 있지만 가장 효율적인 방법은 힙(heap)을 이용하는 것이다.

그 이유는 시간 복잡도를 계산해보면 알 수 있다.

 

스택, 큐 등과 같은 자료구조에서는 요소의 삽입과 삭제가 가장 중요한 요소로 다루어진다. 따라서 시간 복잡도를 계산할 때에는 삽입과 삭제의 복잡도를 따져봐야 한다. 본 글에서는 자세히 설명하지 않겠지만 간단히 말해서, 요소를 삽입하거나 삭제할 때 모든 노드들을 방문하여 우선순위를 확인해야 하는데 여기서 O(n)이라는 시간 복잡도가 계산된다. 이는 곧 입력되는 노드의 개수에 비례하여 계산 시간이 소요된다는 뜻이다.

 

출처:&nbsp;https://vishalgembali191.medium.com/the-big-o-notation-2fe19540b964

 

하지만 힙을 사용하면 삽입과 삭제 연산 모두 O(log₂n) 으로, 훨씬 효율적인 연산을 수행할 수 있다.

예를 들어 n=1024라고 했을 때 O(n)가 1024초 걸린다면, O(log2n)는 10초밖에 걸리지 않는다. 노드가 많아질수록 이 차이는 기하급수적으로 벌어질 것이다.

 

 

힙이란 무엇인가?

힙은 여러 개의 값들 중에서 가장 큰 값이나(max heap) 가장 작은 값을(min heap) 빠르게 찾아내도록 만들어진 자료구조이다.(본 포스트에서는 max heap을 전제로 설명한다.)

즉 부모노드의 키 값이 자식 노드의 키 값보다 큰 완전이진트리를 말한다.

그 모습이 무언가가 잔뜩 쌓여있는 더미(heap)의 모습처럼 보여 힙이라고 부른다.

그런데 위 그림을 보자. 얼핏 생각했을 때는 완전 정렬된 형태의 이진 트리를 생각했을지도 모르겠다.

하지만 그림을 보면 왼쪽과 오른쪽 자식 노드끼리는 정렬이 되어있지 않은 것 같다. 부모노드의 키 값이 자식 노드의 키 값보다 크기만 하면 상관이 없기 때문이다. 이를 반정렬 상태라고 한다.

 

 

이진트리를 정렬하고 삽입과 삭제 수행하기

개념을 알았다면 실제로 힙이 어떻게 만들어지는지 알아보자.

우선 정렬되지 않은 이진 트리(배열)이 있다면 그것을 힙으로 정렬해야 할 것이다. 힙 정렬 작업은 heapify라고 부른다.

이에 대해서는 https://www.programiz.com/dsa/heap-sort 이 사이트에 굉장히 직관적으로 나와있어서 내가 쓰는 것보다 직접 가서 보는 게 좋을 것 같다.

어쨌든 핵심만 설명하자면 하나의 루트 노드에 대해서 정렬을 하는 것을 heapify라고 하고, 전체 정렬을 하기 위해서는 리프 노드를 제외한 모든 노드를 heapify하면 된다.

그렇게 전체를 정렬하여 max heap을 만들고 나면 삽입과 삭제 작업이 진행된다.

 

삽입

1. 가장 마지막 위치에 새로운 요소를 삽입한다.
2. 부모노드와 비교하여 삽입된 노드가 더 크다면 위치를 교환한다.
3. 삽입 노드가 부모 노드보다 작아질 때까지 2번을 반복한다.

삭제

1. 목표는 루트 노드를 삭제하는 것이다. 힙의 마지막 노드와 루트 노드를 교환한 뒤 루트 노드를 삭제한다.
2. 새로운 루트 노드와 자식 노드들을 비교하여 자식 노드가 더 크다면 교환한다.(이때 자식노드 중 더 큰 값과 교환해야 한다.)
3. 자식 노드가 루트 노드보다 작아질 때까지 2번을 반복한다.

 

중요한 것은 삽입과 삭제가 이루어질 때 항상 하나의 노드에 대하여 heapify를 거친다는 것이다.