[자료구조] 힙, 우선 순위 큐

자료구조

힙 (heap)

두 가지 조건을 만족하는 자료 구조이다.

1. 형태 속성: 힙은 완전 이진 트리여야 한다.

2. 힙 속성: 힙 내에 있는 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같아야 한다.

힙을 통해 정렬 문제를 해결할 수 있고(11, 2, 5, 7, 3 -> 2, 3, 5, 7, 11),

또한 우선순위 큐를 구현할 수 있다.

정렬

여러 개의 데이터 요소들을 특정 순서로 배치하는 것

ex) [4, 1, 6, 2, 8, 5]인 파이썬 리스트

1. 오름차순 배치 -> [1, 2, 4, 5, 6, 8]
2. 내림차순 배치 -> [8, 6, 5, 4, 2, 1]

• 정렬 알고리즘: 데이터를 재배치하는 구체적인 방법

  • 삽입 정렬
  • 선택 정렬
  • 퀵 정렬
  • 합병 정렬

배열로 구현한 힙

• 완전 이진 트리이므로 동적 배열로 구현한다.

해당 힙은 파이썬 리스트로 이렇게 구현이 된 것이다. 한 인덱스가 한 노드를 나타낸다.

왼쪽 자식 인덱스: 인덱스 * 2, 오른쪽 자식 인덱스: 인덱스 * 2 + 1

힙 만들기

이 트리는 힙일까? 힙이 되기 위해서는 두 가지 조건을 만족해야 한다.

1. 형태 속성: 이 트리가 완전 이진 트리인가?의 여부

   • 마지막 레벨 빼고 다 채워져 있고, 마지막 레벨도 왼쪽부터 오른쪽 방향으로 채워져 있으므로 완전 이진 트리가 맞다. -> 형태 속성 충족

2. 힙 속성: 부모 노드가 자식 노드보다 큰 값을 가져야 한다.

   • 노드 2의 데이터는 자식들의 데이터보다 작으므로 충족하지 못함.

따라서 힙이 아니다.

부모 노드보다 자식 노드가 더 클 경우 그 두 노드를 바꿔주면 된다. (heapify)

부모 노드, 왼쪽 자식, 오른쪽 자식 중 가장 큰 노드를 고른다. 가장 큰 노드가 부모 노드가 아니라면 부모 노드와 해당 노드를 바꿔준다. 이런 방식으로 heapify를 해줘서 힙의 조건을 충족할 때까지 반복한다.

시간 복잡도

이미지에서처럼 최악의 경우는, root 노드가 계속 내려가서 leaf 노드까지 내려가는 경우이다.

힙은 완전 이진 트리이기 때문에 높이가 O(log(n))이다. 최악의 경우 heapify에 걸리는 시간은 O(log(n))에 비례하므로 시간 복잡도 또한 O(log(n))이다.

힙 만들기 II

heapify: 파라미터로 넘기는 노드가 힙에서 위치를 찾아간다. 노드 10부터 1까지 순서대로 넣어서 호출하면 어떻게 될까?

노드 6~10까지는 leaf node이므로 heapify를 통해 바뀌는 게 없다. 5부터는 가정을 해야 한다.

노드 2의 이전 노드까지는 heapify가 되어 있기 때문에 이미 힙 속성을 지키고 있다고 할 수 있다. 이 부분에서 노드 2에 heapify를 해준다면..

다음과 같이 노드 2와 그 아래 모든 노드들이 힙 속성을 가지게 된다.

1을 제외한 모든 노드들에 대해 heapify를 해줬기 때문에, 다음과 같이 모든 노드가 이미 힙 속성을 지키고 있게 된다. 이제 root에 heapify를 해 주면,

모든 노드가 힙 속성을 갖고 있으므로, 힙을 만들었다 라고 할 수 있게 되는 것이다.

정리하자면, 마지막 노드부터 반대 순서로 heapify를 해주면 힙으로 만들 수 있는 것이다.

시간 복잡도

힙을 만드는 데 걸리는 시간은?

한 번 heapify할 때 걸리는 시간은 O(log(n))인데, 모든 n개의 노드에 대해 heapify를 하므로, 총 걸리는 시간은 O(nlog(n))이 된다.

힙 정렬

힙을 이용한 정렬 알고리즘

root 노드와 노드 10을 바꿔줬다고 해보자. 그럼 위와 같은 형태로 바뀐다. 힙 속성이 망가진 것이다. 힙 속성을 맞추기 위해 root 노드에 heapify를 호출한다.

이 때, 노드 10은 없는 노드 취급을 해줘야 한다. 데이터가 저장되어 있긴 하지만 없는 것처럼 무시해야 한다.

heapify를 해 주면, 노드 10을 제외하고 힙 속성을 충족하는 힙이 완성된다. root 노드에 12가 저장돼 있다.

이번에도 root 노드를 노드 9와 바꿔준다. 이렇게 한 후 마찬가지로 heapify를 해 주면, 노드 10과 9를 제외하고 힙 속성을 충족하는 힙이 완성된다.

이런 방식으로 계속 마지막 노드와 바꿔준 후 의도적으로 망가뜨린 힙 속성을 다시 충족해주기 위해 heapify를 반복하게 되면..

결국 이렇게 값 순서대로 저장된 트리가 완성된다. 데이터가 오름차순으로 정렬된다. 이러한 방식이 바로 힙 정렬이다.

이를 일반화해서 표현해보면:

힙을 만든다 -> root 노드와 마지막 노드를 바꿔준다. -> (바꾼 노드는 없는 노드로 취급한다) -> 새로운 노드가 힙 속성을 지킬 수 있게 heapify를 호출한다

여기서 2~4번째 순서를 반복해주는 것이다.

만약 내림차순으로 정렬하고 싶을 경우?

- 힙 속성을 반대로 바꾸고(자식 노드의 데이터가 부모 노드의 데이터보다 커야 한다) 똑같은 알고리즘을 적용하면 된다.

힙 정렬 구현해보기

어떤 리스트([None, 6, 1, 4, 7, 10, 3, 8, 5, 1, 5, 7, 4, 2, 1])가 있다고 해 보자. 이 리스트를 힙 정렬하려면

1. 먼저 리스트를 힙으로 만든다
2. root 노드와 마지막 노드의 위치를 바꾼다. 마지막 위치로 간 기존의 root 노드는 이제 힙에서 없다고 가정한다.
3. 새로운 root 노드가 힙 속성을 지킬 수 있게 heapify 한다.
4. 힙에 남아 있는 노드가 없도록 2. 와 3. 을 반복한다.

힙 정렬 시간 복잡도

힙 안에 있는 노드의 개수를 n이라고 했을 때 정렬의 시간 복잡도는 어떻게 될까?

1. 먼저 리스트를 힙으로 만든다: 이 경우 걸리는 시간은 앞에서 썼듯이 O(n*log(n))이다. 이는 한 번의 heapify를 할 때의 시간 복잡도가 O(log(n))이고, 노드의 수가 총 n개이기 때문이다.

2. root노드와 마지막 노드의 위치를 바꾼다: 그냥 두 노드의 위치만 바꿔주는 작업이기 때문에 노드의 개수 n과는 상관없이 항상 O(1)이다.

3. 새로운 root 노드가 힙 속성을 지킬 수 있게 heapify한다: 이 때의 시간 복잡도는 O(log(n))이라고 했다. 2. 와 3. 을 합치면 O(log(n) + 1), 즉 O(log(n))이다.

4. 힙에 남아 있는 노드가 없도록 2. 와 3. 을 반복한다: 힙에는 총 n개의 노드가 있으므로 2, 3, 4단계의 시간 복잡도를 종합하면 O(n*log(n))이라고 할 수 있다.

정리하면

• 힙을 만드는 데 O(n*log(n))
• 만든 힙에서 매번 root 노드를 뽑고 남은 것들을 다시 힙으로 만들어주는 작업을 반복하는 데 O(n*log(n))이 걸린다.

두 시간 복잡도를 합치면 O(2*n*log(n))이고, 시간 복잡도에서 상수는 무시되므로 결국 O(n*log(n))이라고 할 수 있다.

따라서 종합적으로 힙 정렬은 O(n*log(n))의 시간 복잡도를 가지는 정렬 알고리즘인 것이다.

다른 정렬 알고리즘들과의 비교

아래 표에는 힙 정렬과 가장 대표적인 정렬 알고리즘 4개의 시간 복잡도가 있다.

정렬 알고리즘	시간 복잡도
선택 정렬	O(n^2)
삽입 정렬	O(n^2)
합병 정렬	O(n*log(n))
퀵 정렬	평균 O(n*log(n))(최악 O(n^2))
합 정렬	O(n*log(n))

힙 정렬은 선택 정렬과 삽입 정렬(O(n^2))보다는 좋고, 합병 졍렬과 퀵 정렬(O(n*log(n)))과는 비슷한 성능을 내는 정렬 방법이라는 것을 알 수 있다.

우선순위 큐

힙은 크게 두 가지 목적으로 사용되는데, 첫 번째는 정렬이고 두 번째가 우선순위 큐이다.

우선순위 큐는 추상 자료형에 속함(내부적인 구현보다 기능에 집중하게 해주는 개념))

• 데이터를 저장할 수 있다.
• 저장한 데이터가 우선순위 순서대로 나온다.

# 최대 우선순위 큐
priority_queue = MaxPriorityQueue()

# 우선순위 큐에 데이터 삽입
priority_queue.add(5)
priority_queue.add(2)
priority_queue.add(7)
priority_queue.add(8)

# 우선순위 큐 데이터 추출(삭제)
print(priority_queue.pop())
print(priority_queue.pop())
print(priority_queue.pop())
print(priority_queue.pop())

결과

8
7
5
2

가장 우선순위가 높은 데이터부터 처리하고 싶을 때 유용하게 쓸 수 있는 추상 자료형이다.
ex) 고객 문의 처리 시 가장 불만도가 높은 고객의 문의부터 처리하고 싶을 때, 가장 등급이 높은 고객의 문의부터 처리하고 싶을 때

힙을 이용해서 우선순위 큐를 쉽게 만들 수 있다.

힙에 데이터 삽입하기

이 힙에 데이터 15를 삽입한다고 해 보자. 그럼 일단 마지막 노드에 15가 들어가게 되는데, 이 경우 힙 속성을 어기게 된다. 15가 힙 속성을 지키도록 위치를 바꿔줘야 한다.
부모 노드 8보다 크므로 두 개를 바꿔주고, 바꾼 뒤에 위치한 노드를 기준으로 한 부모 노드 14보다 15가 더 크기 때문에 두 개를 다시 바꿔준다. root 노드보단 작으므로 이 때 힙 속성을 지키게 된다.

이 알고리즘을 일반화해보면:

• 힙의 마지막 인덱스에 데이터를 삽입한다.
• 삽입한 데이터와 부모 노드의 데이터를 비교한다.
• 부모 노드의 데이터가 더 작으면 둘의 위치를 바꿔준다.
• 새로 삽입한 노드가 제 위치를 찾을 때 까지 위의 두 과정을 반복한다.

힙에서 최고 우선순위(root 노드) 데이터 추출하기

가장 큰 데이터가 높은 우선순위를 가진다고 가정하자. root 노드인 17을 출력하고 싶을 때, 우선 마지막 노드 10(1)과 바꿔주자. 그 후 마지막 노드를 지우면서 특정 변수에 값을 집어넣자.

1은 자식 노드들의 데이터보다 작으므로 힙 속성을 지키도록 heapify를 해서 root노드 1이 제 자리를 찾아가도록 해 보자.

그럼 결국 1이 노드 9에 위치하게 된다. 마지막은 그냥 return_value를 리턴하면 된다. 이렇게 하면 힙 속성을 어기지 않고 root 노드 데이터를 추출할 수 있다.

이 알고리즘을 일반화해보면:

• root 노드와 마지막 노드를 서로 바꿔 준다.
• 마지막 노드의 데이터를 변수에 저장해 준다.
• 마지막 노드를 삭제한다.
• 변수에 저장한 데이터를 리턴한다. (최고 우선순위 데이터)

힙 삽입, 추출 시간 복잡도

힙의 삽입 연산 시간 복잡도

힙 안에 총 n개의 데이터가 있다고 가정하고 데이터 삽입의 3단계를 봐보자:

1. 힙의 마지막 인덱스에 노드를 삽입한다.
2. 삽입한 노드와 그 부모 노드를 비교해서 부모 노드가 더 작으면 둘의 위치를 바꾸고, 더 크면 그대로 둔다.
3. 부모 노드가 더 작은 경우 삽입한 노드가 올바른 위치를 찾을 때까지 2.를 반복한다.

• 1단계

먼저 힙의 마지막에 노드를 삽입해야 한다. 여기선 힙을 동적 배열로 구현했는데, 동적 배열에 원소를 추가하는 것의 시간 복잡도를 분할 상환 분석하면 O(1)이다.

• 2단계

1. 삽입된 노드의 값과 부모 노드의 값을 비교하는 건 O(1)이 걸린다.
2. 삽입된 데이터가 더 큰 경우 부모 노드와의 위치를 바꿔주는 것도 마찬가지로 O(1)이 걸린다.

즉 2단계에서는 O(2)이 걸리는데 이건 O(1)과 같다.

• 3단계

최악의 경우 2단계를 몇 번이나 반복해야 할까? 최악의 경우는 삽입한 데이터가 leaf 노드부터 시작해서 root 노드까지 올라가는 경우이다. 그럼 힙의 높이만큼 2단계를 반복해야 한다. 힙의 높이는 log(n)에 비례하므로 시간은 O(log(n))이다. 이 말은, 2단계의 시간인 O(1)를 최대 O(log(n))번 반복할 수 있다는 말이므로 결국 시간 복잡도는 O(log(n))이 걸린다.

이것들을 모두 정리해보면:

• 1단계의 O(1)
• 2, 3단계의 O(log(n))

를 더해서 O(1 + log(n))이 되고, 이건 곧 O(log(n))과 같다.

결론적으로, 힙에 데이터(노드)를 삽입하는 연산의 시간 복잡도는 O(log(n))이다.

힙의 추출 연산 시간 복잡도

이번에도 힙에 있는 노드의 개수를 n이라고 하자. 단계별로 나눠서 보자.

1. root 노드와 마지막 노드의 위치를 바꾼다.
2. 마지막 위치로 간 원래 root 노드의 데이터를 별도 변수에 저장하고, 노드는 힙에서 지운다.
3. 새로운 root 노드를 대상으로 heapify해서 망가진 힙 속성을 복원한다.
4. 2단계에서 따로 저장해 둔 최우선순위 데이터를 리턴한다.

• 1단계

root 노드와 마지막 노드의 위치를 바꾸는 건 노드의 개수랑은 전혀 상관 없이 O(1)이 걸린다.

• 2단계

데이터를 변수에 지정하는 건 O(1)이 걸린다.여기선 힙을 동적 배열로 구현했는데, 동적 배열에서 마지막 인덱스의 원소를 삭제하는 건 분할 상환 분석을 하면 O(1)이 걸린다. 이 단계는 O(1 + 1)이 걸리니까, O(1)이 걸리는 것이다.

• 3단계

새로운 root 노드를 대상으로 heapify를 호출해서 망가진 힙 속성을 복원하는 단계이다. 이전에 heapify는 O(log(n))이 걸린다고 배웠다.

• 4단계

변수를 리턴하는 것은 O(1)으로 한번에 할 수 있다.

총 걸리는 시간을 더하면 O(1 + 1 + log(n) + 1)이다. 여기서 1은 다 무시해도 되므로, 힙에서 가장 우선수위가 높은 데이터를 추출하는 연산의 시간 복잡도는 O(log(n))인 것이다.

힙으로 구현한 우선순위 큐 평가

우선순위 큐를 구현할 때는 힙 말고도 다른 자료 구조들을 활용할 수도 있다. 예를 들어:

• 정렬된 동적 배열
• 정렬된 더블리 링크드 리스트

으로도 우선순위 큐를 구현할 수 있다. 이번엔 이 방법들과 힙을 이용한 것을 비교해 볼 것이다.

정렬된 동적 배열

정렬된 동적 배열으로도 우선순위 큐를 구현할 수 있다. 데이터를 삽입하거나 추출해도, 동적 배열이 늘 정렬된 상태를 유지하게 하면 된다.

일단 동적 배열에 데이터가 오름차순 또는 내림차순으로 정렬된 채 있다고 가정하고 새로운 데이터를 삽입할 때를 생각해 보자. 새로운 데이터를 정렬된 동적 배열에 삽입하려면 크게 두 가지 작업을 해야 한다:

• 먼저 새로운 데이터가 어느 위치에 들어가야 하는지를 찾고

• 그 위치에 데이터를 넣어야 한다.

  • 삽입할 위치를 찾는 것은 이진 탐색을 사용하면 O(log(n))이 걸린다.
  • 그리고 그 위치에 데이터를 삽입하는 건 최악의 경우 O(n)이 걸린다.

예를 들어 [3, 5, 6, 8, 9]라는 동적 배열이 있다고 하자. 여기에 1을 삽입하려면 맨 앞에 삽입해야 하고 그럼 기존의 3, 5, 6, 8, 9를 각각 한 인덱스씩 뒤로 밀어서 저장해야 한다. 바로 이럴 때 O(n)이 걸리는 것이다.

이 경우 삽입 연산은 총 O(log(n) + n)이 걸리고, 이는 곧 O(n)과 같다.

결국, 정렬된 동적 배열에 데이터를 삽입하는 연산은 O(n)이 걸린다.

데이터를 추출하는 연산은 얼마나 걸릴까? 동적 배열이 항상 정렬된 상태라면 가장 우선순위가 높은 데이터는 항상 배열의 끝에 있을 것이다. 그래서 추출할 때는 그냥 마지막 데이터를 삭제함과 동시에 리턴하면 된다.

동적 배열 맨 뒤에 있는 데이터를 추출하는 연산은 O(1)이 걸린다.

결국, 정렬된 동적 배열에서 가장 우선순위가 높은 데이터를 추출하는 연산은 O(1)이 걸린다.

정렬된 더블리 링크드 리스트

정렬된 더블리 링크드 리스트로 우선순위 큐를 구현한다고 생각해보자.

데이터 삽입은 얼마나 걸릴까? 일단 데이터를 삽입해야 하는 위치를 찾아야 한다. 링크드 리스트에서는 이럴 때 선형 탐색을 해야 한다. 그러니까 헤드 노드에서부터 순서대로 하나씩 노드를 확인하면서 삽입할 위치를 찾아야 한다. 총 노드 수가 n이라고 했을 때, 최악의 경우 n개의 노드를 다 봐야 한다.

예를 들어, | 3 | 5 | 6 | 8 | 9 | 이렇게 정렬된 더블리 링크드 리스트에서 10을 삽입하고 싶으면 선형 탐색으로 3부터 9까지를 다 확인해야 한다.

9 뒤에 삽입해야 한다는 것을 알기 위해 n개의 노드를 다 봐야 하는 것이다. 그러니까 삽입할 위치를 찾는 단계는 O(n)이 걸린다. 그럼, 삽입은 얼마나 걸릴까? 위치만 정해지고 나면 링크드 리스트에서 데이터를 삽입하는 건 O(1)에 할 수 있다.

결국 정렬된 더블리 링크드 리스트에 데이터를 삽입하는 것은 O(1 + n)이 걸리고, 이는 O(n)과 같다.

그럼, 데이터 추출은 얼마나 걸릴까? 더블리 링크드 리스트에서 마지막 데이터를 추출하는 데에는 O(1)이 걸린다. 결국, 정렬된 더블리 링크드 리스트에서 가장 우선순위가 높은 데이터를 추출하는 데 O(1)이 걸리는 것이다.

힙

힙으로 우선순위 큐를 구현했을 때는 어땠을까? 힙에 데이터를 삽입하는 연산과 추출하는 연산의 시간 복잡도는 모두 O(log(n))이었다. 위 내용을 모두 정리하면 아래 표와 같다.

	데이터 삽입	데이터 추출
정렬된 동적 배열	O(n)	O(1)
정렬된 더블리 링크드 리스트	O(n)	O(1)
힙	O(log(n))	O(log(n))

우선순위를 사용할 때

• 정렬된 동적 배열이나 정렬된 링크드 리스트를 사용하면 데이터를 추출할 때 더 효율적이고
• 힙을 사용하면 데이터를 삽입할 때 더 효율적

이라는 것을 알 수 있다.

우선순위 큐는 무엇으로 구현하는 게 제일 좋을까?

만약 새로운 데이터를 삽입할 일이 많으면 힙으로, 기존 데이터를 추출할 일이 더 많으면 정렬된 동적 배열이나 정렬된 더블리 링크드 리스트로 구현하는 게 좋을 것이다.

이렇게 우선순위 큐와 같은 어떤 추상 자료형을 구현할 때는 특정 방식이 더 낫다고 단정하기 힘들다. 단지, 개발자가 처한 상황에 따라 정답이 달라질 뿐이고, 개발자는 이러한 것을 잘 판단해야한다.