[고급 자료구조] Tree: Heap

1. Heap 이란?

• 최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조 입니다.
• 완전 이진트리 기반 입니다.
• 우선순위 큐 구현에 사용됩니다.

 

완전 이진트리

• 마지막 레벨을 제외한 모든 노드가 채워져 있는 이진트리 자료구조 입니다.
• 마지막 레벨은 왼쪽부터 채워져 있어야 합니다.

 

인덱스

• 모든 노드를 배열로 표현할 수 있습니다.
• 노드 간 관계를 배열 인덱스를 통해 접근할 수 있습니다.

왼쪽 자식 노드 index	index*2 + 1
오른쪽 자식 노드 index	index*2 + 2
부모 노드 index	(index-1) / 2

 

2. 종류

최대 힙

• 부모 노드가 자식 노드보다 크거나 같은 값을 가집니다.

 

최소 힙

• 부모 노드가 자식 노드보다 작거나 같은 값을 가집니다.

 

3. 연산

Heapify

• 전체 배열을 힙 구조로 만드는 연산입니다.
• 리프노드를 제외한 레벨의 역순으로 root까지 bubble down 연산을 반복적으로 수행합니다.

 

Bubble down

• 힙의 속성을 유지하도록 만드는 연산입니다.
• 루트노드에서 시작하여 부모가 왼쪽 자식 혹은 오른쪽 자식보다 크면 스왑합니다.
• pop 연산에서 사용됩니다.

 

Bubble up

• 새로운 원소가 힙에 추가될 때, 그 원소가 힙의 속성을 유지하도록 만드는 연산입니다.
• 자식과 부모를 비교하고, 자식의 값이 부모보다 작으면 둘을 교환합니다.
• push 연산에서 사용됩니다.

 

Push

• 맨 끝에 새로운 원소를 추가합니다.
• 새로운 원소를 기준으로 bubble up 연산을 수행합니다.

 

Pop

• 루트 원소를 제거하고, 마지막 원소를 루트로 옮긴 다음 수행합니다.
• 루트를 기준으로 bubble down을 수행합니다.

 

public class MyHeap {
    private int[] arr;
    private int cnt; // number of items

    public MyHeap(int cap) {
        this.arr = new int[cap];
        this.cnt = 0;
    }

    public int pop() {
        if (cnt == 0) return 0;

        int top = arr[0];

        arr[0] = arr[--cnt];
        bubbleDown(0);

        return top;
    }
        
    public void push(int node) {
        if (cnt == size) return;

        arr[cnt] = node;

        bubbleUp(cnt++);
    }

    private void heapify() {
        for (int i = (cnt-2)/2; i >= 0; i--) bubbleDown(i);
    }

    private void bubbleUp(int cIdx) {
        if (cIdx <= 0) return;

        int pIdx = (cIdx-1) / 2;

        if (arr[pIdx] <= arr[cIdx]) return;

        swap(cIdx, pIdx);
        bubbleUp(pIdx);
    }

    private void bubbleDown(int pIdx) {
        int cIdx = pIdx * 2 + 1, rcIdx = cIdx + 1;

        if (cIdx >= cnt) return;
        if (rcIdx < cnt && arr[cIdx] > arr[rcIdx]) cIdx = rcIdx;
        if (arr[pIdx] <= arr[cIdx]) return;

        swap(cIdx, pIdx);
        bubbleDown(cIdx);
    }

    private void swap(int src, int dest) {
        int tmp = arr[src];
        arr[src] = arr[dest];
        arr[dest] = tmp;
    }
}

Time Complexity: O(log n)

 

4. 사용 사례

우선순위 큐

 

 

 

출처 

• Wiki - Heap
• Wiki - Binary Tree