[자료구조] 힙과 우선순위큐에 대하여

힙?

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

• A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
• 힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 ‘최대 힙’, 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 ‘최소 힙’이라고 부른다.
• 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.
• 각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다.
• 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

• 최대 힙

  algorithm upHeap(Position v):
  while (not isRoot(v)) and key(parent(v))>key(v) do
  {
   swapItems(v,parent(v));
   v<-parent(v);
  }

• 최소 힙

  algorithm downHeap(Position v):
  while not (isExternal(leftChild(v)) and isExternal(rightChild(v)) do
  {
  if isExternal(rightChild(v)) then v<-leftChild(v)
  else if key(leftChild(v))<=key(rightChild(v))
    then v<-leftChild(v) else v<-rightChild(v);
  if key(parent(v)) > key(v) then swapItems(v,parent(v))
    else break;
  }

• 힙정렬 정렬 중에 selection, bubble, insertion sort는 기본으로 구현할 줄 알아야 하고, quick sort와 heap sort까지는 해봐야한다고 해서! :) 근데 어렵당. 어려워요 어려웡 힙정렬 구현

우선순위 큐?

알고리즘을 풀 때, 최댓값/최솟값을 구하는 문제는 heap을 사용하면 좋다고 한다.

heap을 배열이나 링크드리스트로 구현해서 풀어도 참 좋겠지만, java의 PriorityQueue API를 써도 참 좋다☺️

사실 힙문제를 배열로 구현해서 푸는 중에, 최소값 2개를 제거하고 값을 삽입 후 정렬을 하는데 정렬된 원소들을 앞으로 당기지 않으면 root 인덱스가 왔다갔다해서 반복수행하기가 힘들었다.

우선순위 큐는 힙을 베이스로 하는 자료구조 라는 것을 보고, 우선순위 큐에 대해 간단히 정리할 예정이다.

난 자바를 사용하니, java.util에 있는 PriorityQueue에 대한 설명을 가져온다.

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. …(중략)… Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueueinstance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueue class.

[출처] https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html

간단히 요약하자면

• 우선순위 큐는 우선순위 힙을 베이스에 둠
• 각 원소는 일반적인 ordering rule이나 큐 생성 시점에 Comparator의 구현을 따름 null element를 허용하지 않음
• 일반적인 ordering rule을 따르기 때문에 비교할 수 없는 객체를 삽입하면 ClassCastException 던짐
• thread safe하지 않으니, multiple threads 환경에서는 PriorityBlockingQueue를 사용하라는 notice

이 외에도 내용이 많지만, 자세한건 출처를 참고하자. 결국 힙으로 만든 거니까, 힙을 사용할 수 있는 알고리즘 문제에서 이 PriorityQueue를 사용해서 풀면 좀 더 간단히 답을 도출할 수 있을 것 같다😍