16장 힙으로 우선순위 유지하기

• 힙은 데이터 세트에서 가장 큰, 또는 가장 작은 데이터 원소를 계속 알아내야 할 때 특히 유용하다.
• 힙의 기능을 제대로 파악하기 위해 지금까지 보지 못했던 새로운 자료 구조인 우선순위 큐부터 살펴보자.

1. 우선순위 큐

• 9.5장에서 배웠던 큐는 FIFO 방식으로 항목을 처리하는 리스트였다.
• 근본적으로 큐 끝에서만 데이터를 삽입하고 큐 앞에서만 접근과 삭제를 수행한다.
• 큐의 데이터에 접근하려면 데이터가 삽입됐던 순서를 따라야 한다.
• 우선순위 큐(Priority Queue)는 삭제와 접근에 있어 전형적인 큐와 흡사하나 삽입에 있어 정렬된 배열과 비슷한 리스트다.
• 즉 우선순위 큐 앞에서만 데이터에 접근하고 삭제하되 데이터를 삽입할 때는 데이터를 늘 특정 순서대로 정렬시킨다.
• 우선순위 큐는 추상 데이터 타입의 한 예다. 다시 말해 기초적인 자료구조로 구현할 수 있다.
• 우선순위 큐를 간단하게 구현하려면 정렬된 배열을 이용하면 된다.
• 배열을 사용하되 다음의 제약이 필요하다.
  • 데이터를 삽입할 때 항상 적절한 순서를 유지한다.
  • 데이터는 배열 끝에서만 삭제한다.(배열의 끝이 우선순위 큐의 앞이다.)
• 우선순위 큐의 주요 연산은 삽입과 삭제다.
• 1장에서 봤듯이 배열 앞에서 삭제는 인덱스 0의 빈 자리를 메우기 위해 모든 데이터를 옮겨야 하므로 O(N)이다.
• 하지만 영리하게 구현을 바꿔 배열 끝을 우선순위 큐 앞으로 삼았다. 이렇게 하면 항상 배열 끝에서 삭제하니 O(1)이다.
• 삽입은 어떨까?
• 정렬된 배열에서 삽입은 새 데이터를 넣을 자리를 알아내기 위해 배열의 원소를 모두 확인해야 하기 때문에 O(N)이다.
• 따라서 배열 기반 우선순위 큐는 삭제가 O(1), 삽입이 O(N)이다.
• 그러나 다른 자료구조를 사용하면 어떨까?

2. 힙

• 힙에는 몇 가지 종류가 있으나 이진 힙(Binary Heap)을 보자.
• 이진 힙은 특수한 종류의 이진 트리다.
• 이진 트리는 각 노드에 최대 자식 노드가 둘인 트리였다.
• 이진 힙에는 최대 힙(max-heap)과 최소 힙(min-heap) 두 종류가 있다.
• 힙은 다음의 조건을 따르는 이진 트리다.
  • 각 노드의 값은 그 노드의 모든 자손 노드의 값보다 커야 한다. 이 규칙을 힙 조건(Heap Condition)이라 부른다.
  • 트리는 완전(Complete)해야 한다.

2.1 힙 조건 Heap condition

• 최대 힙에서 힙 조건이란 각 노드의 값이 그 노드의 모든 자손 노드보다 커야 한다는 뜻이다.
• 이진 탐색 트리에서 각 노드의 오른쪽 자식은 그 노드보다 크다.
• 반대로, 힙에서 노드는 그 노드의 모든 자손보다 크다.
• 최소 힙은 최대 힙의 힙 조건의 반대 조건을 가진다. 즉, 각 노드의 값이 그 노드의 모든 자손 노드보다 작다.

2.2 완전 트리 Complete tree

• 완전 트리는 빠진 노드 없이 노드가 완전히 채워진 트리다.
• 따라서 트리의 각 층(레벨)을 왼쪽부터 오른쪽으로 읽었을 때 모든 자리마다 노드가 있다.
• 하지만 바닥 줄에는 빈 자리가 있을 수 있다.
• 단 빈 자리의 오른쪽으로는 어떤 노드도 없어야 한다.

3. 힙 속성

• 힙 조건에 따라 힙은 특정 방식으로 정렬되지만 이러한 정렬은 힙에서 값을 검색하는 데 전혀 도움이 되지 않는다.
• 힙에는 자손이 조상보다 클 수 없다는 분명한 순서가 있지만 값을 검색하기에는 부족하다.
• 따라서 힙은 이진 탐색 트리에 비해 약한 정렬(weakly ordered)이라고 말한다.
• 힙에서는 루트 노드가 항상 최댓값이다.
• 힙의 주요 연산은 삽입과 삭제다.
• 힙에서 검색하려면 각 노드를 검색해야 하므로 힙으로는 대개 검색 연산을 구현하지 않는다.
• 힙에는 마지막 노드(last node)가 있다. 이는 바닥 레벨에서 가장 오른쪽에 위치한 노드다.

4. 힙 삽입

• 힙에 새 값을 삽입하려면 다음 알고리즘을 수행한다.
  1. 새 값을 포함하는 노드를 생성하고 바닥 레벨의 가장 오른쪽 노드 옆에 삽입한다. 즉, 이 값이 힙의 마지막 노드가 된다.
  2. 새로 삽입한 노드와 그 부모 노드를 비교한다.
  3. 새 노드가 부모 노드보다 크면 새 노드와 부모 노드를 스왑한다.
  4. 새 노드보다 큰 부모 노드를 만날 때까지 3번 단계를 반복하며 새 노드를 힙 위로 올린다.
• 새 노드를 힙 위로 올리는 과정을 노드를 위로 트리클링(trickling)한다고 표현한다.
• 힙 삽입의 효율성은 O(logN)이다.

5. 마지막 노드 탐색

• 삽입 알고리즘이 상당히 간단해 보인다. 그러나 작은 문제가 있다. 마지막 노드 자리를 어떻게 찾아야 할까?
• 이 문제를 마지막 노드 문제라고 부르자. 우선 삭제 연산을 알아보고, 나중에 다룬다.

6. 힙 삭제

• 힙에서 값을 삭제하려면 루트 노드만 삭제할 수 있다는 점을 먼저 알아야 한다.
• 이는 가장 높은 우선순위를 갖는 항목만 접근하고 삭제하는 우선순위 큐의 동작 방식과 일치한다.
• 힙의 루트 노드를 삭제하는 알고리즘은 다음과 같다.
  1. 마지막 노드를 루트 노드 자리로 덮어쓴다. 결과적으로 원래 루트 노드는 삭제된다.
  2. 루트 노드를 적절한 자리까지 트리클링한다.
• 어떻게 루트 노드를 적절한 자리까지 트리클링할 수 있을까? 트리클링하는 노드를 트리클 노드라고 부르겠다.
  1. 트리클 노드의 두 자식을 확인해 어느 쪽이 더 큰지 확인한다.
  2. 트리클 노드가 두 자식 노드 중 큰 노드보다 작으면 큰 노드와 트리클 노드를 스왑한다.
  3. 트리클 노드에 그 노드보다 큰 자식이 없을 때까지 1, 2단계를 반복한다.
• 트리클 노드와 두 자식 중 큰 노드를 스왑하는 이유는 작은 노드와 스왑하면 힙 조건이 바로 깨지기 때문이다.
• 즉, “두 자식 중 큰 노드”가 “두 자식 중 작은 노드”의 자식이 된다.
• 힙에서 삭제하려면 루트부터 시작해 log(N)개 레벨을 거쳐 노드를 트리클링해야 하므로 삽입과 마찬가지로 O(logN)이다.

7. 힙 대 정렬된 배열

정렬된 배열 힙

삽입	O(N)	O(logN)
삭제	O(1)	O(logN)

• 다시 비교해 보자.

정렬된 배열 힙

삽입	느림	매우 빠름
삭제	무지하게 빠름	매우 빠름

• 때로 무지하게 빠르지만 느릴 수도 있는 자료구조를 쓰는 것보다 일관되게 매우 빠른 자료구조를 사용하는 편이 낫다.
• 보통 우선순위 큐를 사용할 때는 삽입과 삭제를 거의 비슷한 비율로 수행한다.

8. 다시 살펴보는 마지막 노드 문제

• 마지막 노드 문제를 풀기 전에 왜 삽입과 삭제에 마지막 노드가 꼭 필요한지부터 알아보자.
• 새 값을 힙의 다른 위치에 삽입하면 안 될까?
• 삭제할 때 루트 노드를 마지막 노드 대신 다른 노드로 대체할 수는 없을까?
• 다른 노드와 바꾸는 경우를 생각해 보자.
  • 힙이 불완전해진다는 사실을 곧 깨닫게 된다.
  • 왜 힙에서는 완전성(completeness)이 그토록 중요할까?
  • 이유는 균형 잡힌 힙으로 유지하고 싶어서다.
• 균형 잡힌 힙은 일관되게 O(logN)안에 연산이 가능하다.
• 그러나 불균형이 심한 트리는 최악의 경우 O(N) 단계가 필요하다.

9. 배열로 힙 구현하기

• 마지막 노드 찾기는 힙 연산의 핵심이고 또한 효율적으로 찾아야 하므로 주로 배열을 사용해 힙을 구현한다.
• 즉, 힙 자체가 내부적으로 배열을 사용하는 추상 데이터 타입일 수 있다.
• 힙을 배열로 구현하는 이유는 마지막 노드 문제를 해결하기 위해서다. 어떻게 해결할까?
• 아래의 그림처럼 힙을 구현하면 마지막 노드는 항상 배열의 마지막 원소다.

• 아주 간단하게 마지막 노드를 찾을 수 있다.

9.1 배열 기반 힙 순회

• 앞서 봤듯이 힙 삽입과 삭제 알고리즘이 가능하려면 힙을 트리클링할 수 있어야 한다.
• 하지만 힙이 내부적으로 배열인데, 어떤 노드가 어떤 노드와 연결되는지 어떻게 알 수 있을까?
• 위의 그림과 같이 힙 노드에 인덱스를 할당하면 다음과 같은 힙 특성을 항상 만족한다.
  • 어떤 노드의 왼쪽 자식은 index * 2 + 1 에 위치한다.
  • 어떤 노드의 오른쪽 자식은 index * 2 + 2 에 위치한다.

9.2 대안 구현

• 내부적으로 배열을 써서 힙을 구현했으나 연결 리스트로도 구현할 수 있다.
• 사실 배열을 사용하면 15장에 나왔던 이진 탐색 트리를 비롯해 어떤 종류의 이진 트리든 구현할 수 있다.
• 하지만 힙은 마지막 노드를 쉽게 찾아준다는 점에서 배열로 구현하면 유리한 첫 이진 트리 사례다.

10. 우선순위 큐로 쓰이는 힙

• 우선순위 큐로 돌아가 보자.
• 우선순위 큐의 주요 메소드는 큐에서 가장 높은 우선순위를 갖는 항목에 바로 접근하는 것이다.
• 그래서 우선순위 큐 구현에는 힙이 딱 어울린다.
• 힙에서는 가장 높은 우선순위의 항목이 항상 루트 노드에 있으니 바로 접근할 수 있다.
• 결국 힙의 약한 정렬이 굉장한 장점으로 작용했다.
• 완벽히 정렬할 필요가 없으니 새 값을 항상 O(logN)시간에 삽입할 수 있다.
• 동시에 힙은 언제든 필요한 항목에, 즉 힙의 최댓값에 항상 접근할 수 있을 만큼 정렬되어 있다.

 

 

• 다음 장부터 난이도 급상승 예정…