자료 구조 (6) : 우선순위 큐(Priority Queue) & 힙(Heap)

우선순위 큐

가장 높은 우선순위를 갖는 데이터가 먼저 나오는 자료 구조

 

• 주요 연산
  
  • Adding(add) : 우선순위 큐에 데이터를 삽입
  • Polling(poll)  : 가장 높은 우선순위의 데이터를 제거 후 반환
  • Peeking(peek) : 가장 높은 우선순위의 데이터를 반환(제거하지 않음)
• 사용 상황(우선순위에 따라 자료를 꺼내야 하는 경우)
  • 최단 경로 알고리즘(다익스트라)
  • 최소 스패닝 트리(MST) 알고리즘(프림)
  • 프로세스 스케줄링
• 시간 복잡도

	힙
삽입(Adding)	O(logN)
다음 값 삭제(Polling)	O(logN)
다음 값 조회(Peeking)	O(1)
이진 힙 생성	O(N)
특정 값 제거(Removing)	O(N)
해시 테이블 활용 특정값 제거(Removing)	O(logN)
포함 확인(Contains)	O(N)
해시 테이블 활용 포함 확인(Contains)	O(1)

 

* 힙으로 구현한 우선순위 큐는 다른 우선순위 큐에 비해 많은 연산에서 시간 복잡도의 이점이 존재

* 해시 테이블 활용 시 추가 공간이 필요하고 해시 테이블을 사용하는 오버헤드가 발생하는 단점이 존재

 

힙

힙 속성을 만족하는 완전이진트리 기반 자료 구조

 

* 힙 속성 : A가 B의 부모노드이면, A의 키값과 B의 키값 사이에는 대소관계가 성립

* 완전이진트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며 모든 노드는 가능한 한 왼쪽에 위치

 

• 종류
  • 최대힙 : 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙
  • 최소힙 : 부모노드의 키값이 자식노드의 키 값보다 항상 작은 힙
• 연산 과정
  • Adding : 마지막 노드 위치에 데이터를 넣고 부모 노드와 대소관계를 비교하면서 루트 노드 까지 Swap
  • Polling
    1. 루트를 제거하고 반환 후 마지막 노드 값을 제거 후 루트에 넣기
    2. 자식 노드 값 중 루트보다 우선순위가 높은 값이 있을 때, 그 값들 중 더 우선순위가 높은 값과 현재 값을 Swap
    3. 마지막 레벨까지 2번 단계를 반복
  • Removing
    1. 해당 값이 존재하는 노드를 선형 탐색 후, 해당 값을 반환(제거) 후 마지막 노드 값을 제거 후 루트에 넣기
    2. 제거한 값과 마지막 노드 값의 우선순위를 비교하여 부모 노드(Bubble Up)와 자식 노드(Bubble Down) 중 비교할 곳 정하기
    3. 다음 노드와 우선순위를 비교하면서 루트 노드(Bubble Up) 혹은 마지막 레벨(Bubble Down)까지 Swap

 Priority Queue 구현 예시

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class BinaryHeap<T extends Comparable<T>> {

  private List<T> heap = null;

  public BinaryHeap() {
    this(1);
  }

  public BinaryHeap(int size) {
    heap = new ArrayList<>(size);
  }

  public BinaryHeap(T[] elems) {

    int heapSize = elems.length;
    heap = new ArrayList<T>(heapSize);

    for (int i = 0; i < heapSize; i++) heap.add(elems[i]);

    for (int i = Math.max(0, (heapSize / 2) - 1); i >= 0; i--) sink(i);
  }

  public BinaryHeap(Collection<T> elems) {

    int heapSize = elems.size();
    heap = new ArrayList<T>(heapSize);

    heap.addAll(elems);

    for (int i = Math.max(0, (heapSize / 2) - 1); i >= 0; i--) sink(i);
  }

  public boolean isEmpty() {
    return size() == 0;
  }

  public int size() {
    return heap.size();
  }

  public T peek() {
    if (isEmpty()) return null;
    return heap.get(0);
  }

  public T poll() {
    return removeAt(0);
  }

  public boolean contains(T elem) {
    for (int i = 0; i < size(); i++) if (heap.get(i).equals(elem)) return true;
    return false;
  }

  public void add(T elem) {

    if (elem == null) throw new IllegalArgumentException();

    heap.add(elem);

    int indexOfLastElem = size() - 1;
    swim(indexOfLastElem);
  }

  private boolean less(int i, int j) {
    T node1 = heap.get(i);
    T node2 = heap.get(j);
    return node1.compareTo(node2) <= 0;
  }

  private void swim(int k) {

    int parent = (k - 1) / 2;

    while (k > 0 && less(k, parent)) {
      swap(parent, k);
      k = parent;

      parent = (k - 1) / 2;
    }
  }

  private void sink(int k) {
    int heapSize = size();
    while (true) {
      int left = 2 * k + 1;
      int right = 2 * k + 2;
      int smallest = left;

      if (right < heapSize && less(right, left)) smallest = right;

      if (left >= heapSize || less(k, smallest)) break;

      swap(smallest, k);
      k = smallest;
    }
  }

  private void swap(int i, int j) {
    T elem_i = heap.get(i);
    T elem_j = heap.get(j);

    heap.set(i, elem_j);
    heap.set(j, elem_i);
  }

  public boolean remove(T elem) {
    if (elem == null) return false;
    for (int i = 0; i < size(); i++) {
      if (elem.equals(heap.get(i))) {
        removeAt(i);
        return true;
      }
    }
    return false;
  }

  private T removeAt(int i) {
    if (isEmpty()) return null;

    int indexOfLastElem = size() - 1;
    T removed_data = heap.get(i);
    swap(i, indexOfLastElem);

    heap.remove(indexOfLastElem);

    if (i == indexOfLastElem) return removed_data;
    T elem = heap.get(i);

    sink(i);

    if (heap.get(i).equals(elem)) swim(i);
    return removed_data;
  }
}