힙(Heap)

1. 힙(Heap)이란?

- 힙은 완전 이진 트리 형태로 구성되는 자료구조로 각 노드가 특정 순서(우선순위)를 만족하도록 구성된다.

- 부모 노드의 값이 자식 노드의 값보다 작거나 같아 루트 노드에 최솟값이 있는 최소 힙(Min Heap)과 부모 노드의 값이 자식 노드의 값보다 크거나 같아 루트 노드에 최댓값이 있는 최대 힙(Max Heap)으로 구성된다.

- 우선순위 큐의 기본 구현체로 사용되며 삽입과 삭제 연산이 O(logN)의 복잡도를 가지며 힙 정렬과 다익스트라 알고리즘에 활용된다.

 

2. 자바를 활용한 힙 구현

- 배열 기반의 최대 힙을 구현한 예제이다.

public class MaxHeap {
    private int[] heap;
    public int size;
    private int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        heap = new int[capacity];
        size = 0;
    }
    
    // 부모, 왼쪽 자식, 오른쪽 자식 인덱스 계산
    private int parent(int index) {
        return (index - 1) / 2;
    }
    
    private int leftChild(int index) {
        return 2 * index + 1;
    }
    
    private int rightChild(int index) {
        return 2 * index + 2;
    }
    
    // 삽입: 새로운 값을 배열의 마지막에 추가한 후 상향식으로 정렬
    public void insert(int value) {
        if (size == capacity) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = value;
        int current = size;
        size++;
        
        // 부모와 비교하여, 현재 값이 더 크면 swap
        while (current > 0 && heap[current] > heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }
    
    // 삭제: 루트를 제거한 후 마지막 요소를 루트로 배치하고 하향식으로 정렬
    public int poll() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int result = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return result;
    }
    
    private void heapifyDown(int index) {
        int largest = index;
        int left = leftChild(index);
        int right = rightChild(index);
        
        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != index) {
            swap(index, largest);
            heapifyDown(largest);
        }
    }
    
    private void swap(int i, int j) {
        int tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }
    
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(5);
        maxHeap.insert(3);
        maxHeap.insert(8);
        maxHeap.insert(1);
        
        while (maxHeap.size > 0) {
        	// 출력: 8 5 3 1
        	System.out.print(maxHeap.poll() + " ");
        }
    }
}