[Algorithm] 23 우선순위 큐와 힙

우선순위 큐와 힙

• 우선순위 큐는 일반 큐와는 달리 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 자료구조
• 수행할 작업이 여러 개 있고 시간이 제한되어 있을 때 우선순위가 높은 것부터 수행하는 경우 사용

우선순위 큐를 구현하는 방법

1. 연결리스트, 배열
   1. 자료구조에 원소를 모두 집어넣고, 원소를 꺼낼 때 마다 모든 원소를 순회하며 우선순위가 높은 원소를 찾는 방식을 사용해야 하는데, 이러면 원소 추가 O(1), 검색 O(n)이 걸린다.
2. 균형잡힌 이진 검색 트리
   1. 구현이 어렵다.
   2. 원소들을 우선순위로 정렬해 두면 최대 원소 삭제와 원소 삽입 모두 O(logN) 시간에 할 수 있다.
3. 힙
   1. 가장 큰 원소를 찾는 데 최적화된 형태의 이진 트리
   2. 이진 검색 트리보다 훨씬 간단한 구조로 구현할 수 있다
   3. 새 원소를 추가하는 연산과 가장 큰 원소를 꺼내는 연산 모두 O(logN) 시간에 할 수 있다.
   4. 우선순위 큐를 구현하는 쉬운 방법으로 힙을 사용한다.
      1. 우선순위와 실제 자료의 쌍을 담는 힙을 만든다
      2. 대소 관계를 비교할 때는 우선순위를 비교한다

힙의 정의

힙은 특정한 규칙을 만족하도록 구성된 이진 트리로, 단순히 최대 원소를 가능한 한 빠르게 찾을 수 있는 방법으로 설계되었다.

힙의 대소 관계 : 힙의 가장 중요한 특징

이 규칙은 부모 자식 관계에만 적용되며 왼쪽 자식과 오른쪽 자식이 갖는 원소의 크기는 제한하지 않는다. 이 규칙에 의해 트리에서 가장 큰 원소는 항상 트리의 루트에 들어가므로 최대 원소를 빨리 찾는 힙의 목적에 부합한다.

힙은 트리의 높이를 항상 일정하게 유지하기 위해 트리의 구조에 제약을 둔다.

힙의 모양 규칙

• 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.
• 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

배열을 이용한 힙 구현

힙의 모양 규칙에 의해, n개의 노드가 있을 때

이 노드들은 arr[0]에서 arr[n-1]까지 순차적으로 대응된다.

• arr[i]의 왼쪽 자식은 arr[2*i + 1]에 대응된다.
• arr[i]의 오른쪽 자식은 arr[2*i + 2]에 대응된다.
• arr[i]의 부모는 arr[(i-1)/2]에 대응된다. (나눗셈 결과는 내림한다.)

새 원소의 삽입

• 힙의 모양 규칙에 따라 새 노드가 트리의 어느 쪽에 생겨나야 할지를 판단한다.

• 그 쪽으로 원소를 내려보내 삽입한다.

  즉, 새 노드는 항상 heap[]의 맨 끝에 추가된다.

• 새 원소를 자신의 부모 노드가 가진 원소와 비교한다. (반복)
• 부모 노드가 가진 원소가 작다면 두 원소의 위치를 바꾼다. (반복)

// 정수를 담는 최대 힙에 새 원소 newValue를 삽입한다.
void push_heap(vector<int>& heap, int newValue) {
  // heap의 맨 끝에 newValue를 삽입한다
  heap.push_back(newValue);
  // 현재 newValue의 위치
  int idx = heap.size() - 1;

  // 루트에 도달하거나 newValue이상의 원소를 가진 조상을 만날 때 까지
	// 부모 노드가 가진 노드가 더 작다면
  while (idx > 0 && heap[(idx - 1) / 2] < heap[idx]) {
    swap(heap[idx], heap[(idx - 1) / 2]);
    idx = (idx - 1) / 2;
  }
}