[Java] Heap (힙)

• 트리 기반의 자료구조
• 최소 힙은 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값
• 주로 배열로 구현
• 부모, 자식 같의 관계만 정의할 뿐 좌우에 대한 관계는 정의하지 않음
• 완전 이진 트리의 형태
• 다익스트라 알고리즘에도 활용

삽입

• 업힙(Up-Heap) 연산을 수행
  
  

• 시간 복잡도: O(log n)

 

추출

• 다운힙(Down-Heap) 연산을 수행

• 시간 복잡도: O(log n)

추출 이후에 다시 힙의 특성을 유지하는 작업이 필요

PriorityQueue

• Java에서는 다음과 같이 PriorityQueue를 Heap으로 사용할 수 있다.

PriorityQueue<Integer> heap = new PriorityQueue<>();

• PriorityQueue 의 코드 내부에서는 Object[] Array를 사용한다. 즉, 고정된 크기의 Array를 사용하여 작업을 수행한다.
• 기본적으로 new PriorityQueue<>()으로 생성했을때 Array의 크기는 11이다. 코드 내부에서 DEFAULT_INITIAL_CAPACITY라는 변수 값이 11이고 이 값으로 Array가 생성된다. 마찬가지로 값을 지정하면 해당 값만큼의 크기로 Array가 생성된다.

1. 삽입

• PriorityQueue는 offer() 메소드를 사용하여 삽입한다.

public boolean offer(E e) {  
    if (e  null)  
        throw new NullPointerException();  
    modCount++;  
    int i = size;  
    if (i >= queue.length)  
        grow(i + 1);  
    siftUp(i, e);  
    size = i + 1;  
    return true;  
}

• 위 구현된 코드를 확인해보면 고정된 크기를 넘었을때 grow()라는 메소드를 호출하는 것을 확인할 수 있다.

1.1 grow()

• grow()에서는 다음과 같이 크기를 1만큼 증가시킨 Array를 새로 생성한 후 값을 복사하는 작업을 수행한다. 즉, 고정된 크기를 넘어설때마다 시간 복잡도 O(n)이 걸린다.

queue = Arrays.copyOf(queue, newCapacity);

1.2 siftUp()

• siftUp()메소드에서는 Comparator 여부에 따라 siftUpUsingComparator()와 siftUpComparable()를 수행한다.
• siftUpUsingComparator()를 기준으로 코드를 보면 부모 노드의 값과 삽입한 값을 비교하여 스왑을 수행하는 것을 확인할 수 있다.

private static <T> void siftUpUsingComparator(  
    int k, T x, Object[] es, Comparator<? super T> cmp) {  
    while (k > 0) {  
        int parent = (k - 1) >>> 1;  
        Object e = es[parent];  
        //x가 더 크면
        if (cmp.compare(x, (T) e) >= 0)  
            break;  
        es[k] = e;  
        k = parent;  
    }  
    es[k] = x;  
}

• k: 마지막 인덱스, x: 삽입한 값, es: heap에서 사용되는 array

현재 노드 위치(k) 기준으로 부모 노드 위치는 (k - 1) >>> 1 이다.

2. 추출

• PriorityQueue는 poll() 메소드를 사용하여 추출한다.

public E poll() {  
    final Object[] es;  
    final E result;  

    if ((result = (E) ((es = queue)[0])) != null) {  
        modCount++;  
        final int n;  
        final E x = (E) es[(n = --size)];  
        es[n] = null;  
        if (n > 0) {  
            final Comparator<? super E> cmp;  
            if ((cmp = comparator)  null)  
                siftDownComparable(0, x, es, n);  
            else  
                siftDownUsingComparator(0, x, es, n, cmp);  
        }  
    }  
    return result;  
}

1. 첫 번째 값을 result에 할당
2. 마지막 값을 x에 할당하고 null 값으로 대체하여 삭제
3. siftDownComparable() 또는 siftDownUsingComparator 수행

x는 Array의 마지막 값이고 리프 노드가 아니다.

2.1 siftDownUsingComparator()

private static <T> void siftDownUsingComparator(  
    int k, T x, Object[] es, int n, Comparator<? super T> cmp) {  
    // assert n > 0;  
    int half = n >>> 1;  
    while (k < half) {  
        int child = (k << 1) + 1;  
        Object c = es[child];  
        int right = child + 1;  
        //오른쪽 자식이 더 작으면
        if (right < n && cmp.compare((T) c, (T) es[right]) > 0)  
            c = es[child = right];  
        //x가 더 작으면
        if (cmp.compare(x, (T) c) <= 0)  
            break;  
        es[k] = c;  
        k = child;  
    }  
    es[k] = x;  
}

• x 를 첫 번째 값으로 두고 자식 노드 왼쪽, 오른쪽과의 비교를 통해 스왑을 수행한다.
• half만큼 수행하는 이유는 half이상의 노드들은 이미 재배치되어있기 때문에 더 이상 스왑이 필요하지 않다.

현재 부모 노드 위치 (k)의 왼쪽 자식 노드의 위치는 (k << 1) + 1 이다.