우선순위 큐: 힙(Priority Queue)

1. 우선순위 큐와 힙

우선순위를 부여하는 기준은 다양하다. 우선순위를 가진 원소를 삽입할 수 있고, 우선순위가 가장 큰 원소를 빼낼 수 있으면 우선순위 큐(Priority Queue)라고 한다.

 

우선순위 큐는 트리처럼 임의의 값을 가진 원소를 검색하는 기능은 필요 없고 가장 높은 것을 알려주고 삭제할 수 있으면 된다.

우선순위 큐도 선형 자료구조를 이용해서 구현할 수 있지만 더 효율적인 방법이 있다. 바로 힙(Heap)이다.

 

힙은 대표적인 우선순위 큐로, 완전 이진 트리 구조를 사용한다.

이진 트리: 모든 노드가 2개 이하의 자식을 갖는 트리
포화 이진 트리: 루트부터 모든 노드가 정확히 자식 노드를 2개씩 가지면서 꽉 채워진 트리
완전 이진 트리: 노드 수가 맞지 않아 포화 이진트리를 만들 수 없는 경우 최대한 가깝게 만들어진 트리
맨 아래 레벨만 가장 왼쪽부터 채워진 상태로 꽉 채워지지 않은 트리다.

 

힙은 아래 두 가지 조건을 만족해야 한다.

1. 완전 이진 트리
2. 힙 특성: 모든 노드는 값을 갖고, 자식 노드 값보다 크거나 같다.

2번 조건을 만족할 때 우선순위가 가장 큰 원소가 루트에 자리하게 된다. 이런 힙을 최대 힙(Max Heap)이라고 한다. 반대로 모든 노드의 값이 자식 노드 값보다 작거나 같은 힙을 최소 힙(Min Heap)이라고 한다.

 

임의의 배열은 항상 완전 이진 트리로 해석할 수 있다. 따라서 배열에 저장한다는 사실 자체가 1번 조건을 자동으로 만족한다.

배열이 A[0]부터 시작된다면 A[k]의 자식은 A[2k+1]과 A[2k+2]가 되고, 부모 노드는 A[(k-1)/2]가 된다.

완전 이진 트리의 중간에 빠지는 노드가 없다는 성질로 인해 배열의 인덱스로 간단히 계산할 수 있다.

 

2. 힙 알고리즘

원소 A[i]의 삽입 과정을 살펴보자.

1. A[i]를 부모 값과 비교해서 힙 특성을 깨면 자리를 바꾼다.
2. 바뀐 부모를 다시 자신의 부모와 비교해서 힙 특성을 만족하지 않으면 바꾼다.

이 과정을 힙 특성을 만족하는 최초의 지점까지 혹은 더 이상 부모 노드가 존재하지 않을 때까지 반복한다.

 

다음은 원소 A[i]의 삭제 과정이다.

1. 루트 노드(A[0]) 자리에 마지막 노드를 복사하고 마지막 노드는 버린다. (배열의 크기를 줄이면 된다.)
2. 루트 노드의 값과 자식 노드의 우선순위를 비교해서 큰 값과 자리를 바꾼다.

마지막 노드가 리프 노드가 될 때까지 이 과정을 반복한다.

 

3. 힙 구현

public interface PQInterface<E> {
    public void insert(E newItem) throws Exception;
    public E deleteMax() throws Exception;
    public E max() throws Exception;
    public boolean isEmpty();
    public void clear();
}

public class PQException extends Exception{
    public PQException(String msg) {
        super(msg);
    }
}

public class Heap<E extends Comparable> implements PQInterface<E> {
    private E[] A;
    private int numItems;

    public Heap(int arraySize) {
        A = (E[]) new Comparable[arraySize];
        numItems = 0;
    }

    public Heap(E[] B, int numElements) {
        A = B;
        numItems = numElements;
    }

    //힙에 원소 삽입하기
    public void insert(E newItem) throws PQException {
        if (numItems < A.length) {
            A[numItems] = newItem;
            percolateUp(numItems);
            numItems++;
        } else throw new PQException("HeapErr: Insert()-Overflow!");
    }

    //스며오르기
    private void percolateUp(int i) {
        int parent = (i - 1) / 2;
        if (parent >= 0 && A[i].compareTo(A[parent]) > 0) {
            E tmp = A[i];
            A[i] = A[parent];
            A[parent] = tmp;
            percolateUp(parent);
        }
    }

    //힙에서 원소 삭제하기
    public E deleteMax() throws PQException {
        if(!isEmpty()) {
            E max = A[0];
            A[0] = A[numItems-1];
            numItems--;
            percolateDown(0);
            return max;
        } else throw new PQException("HeapErr: Deletemax()-Underflow");
    }

    //스며내리기
    private void percolateDown(int i) {
        int child = 2*i + 1;
        int rightChild = 2*i + 2;
        if(child <= numItems - 1) {
            if (rightChild <= numItems - 1 && A[child].compareTo(A[rightChild]) < 0)
                child = rightChild;
            if (A[i].compareTo(A[child]) < 0) {
                E tmp = A[i];
                A[i] = A[child];
                A[child] = tmp;
                percolateDown(child);
            }
        }
    }

    //힙 만들기
    public void buildHeap() {
        if (numItems >= 2)
            for (int i=(numItems - 2) / 2; i>=0; i--)
                percolateDown(i);
    }

    //힙의 최댓값 구하기
    public E max() throws PQException {
        if (!isEmpty()) {
            return A[0];
        } else throw new PQException("HeapErr: Max()-Empty!");
    }

    @Override
    //힙이 비어있는지 확인하기
    public boolean isEmpty() {
        return numItems == 0;
    }

    //힙 비우기
    public void clear() {
        A = (E[]) new Comparable[A.length];
        numItems = 0;
    }

    public static void main(String[] args) throws Exception {
        Heap<Integer> h = new Heap<>(5);
        try {
            h.insert(1);
            h.insert(10);
            h.clear();
            h.insert(30);
            h.insert(10);
            h.insert(30);
            h.insert(20);
            h.insert(40);
            h.deleteMax();
            h.insert(1);
            h.insert(3); //HeapErr: Insert()-Overflow!
            h.deleteMax();
        } catch (PQException e) {
            String msg = e.getMessage();
            System.out.println(msg);
        }
    }
}