힙(Heap)

힙(Heap)

힙 자료구조(Heap)는 이진 트리(Binary Tree)의 일종으로, 우선순위 큐(Priority Queue)를 구현하기 위해 자주 사용된다. 힙은 두 가지 주요 조건을 만족한다.

• 힙 속성(Heap Property):
  • 최대 힙(Max-Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
  • 최소 힙(Min-Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같다.
• 완전 이진 트리(Complete Binary Tree)
  • 마지막 레벨을 제외한 모든 레벨은 노드가 꽉 차 있어야 하며, 마지막 레벨의 노드는 왼쪽부터 채워진다.

힙의 사용 사례

• 우선순위 큐: 작업을 우선순위에 따라 처리할 때 사용된다.
• 정렬(힙 정렬): 정렬 알고리즘 중 하나로, 시간 복잡도가 O(n log n)이다.
• 그래프 알고리즘: 다익스트라와 프림알고리즘에서 최소 비용을 빠르게 찾기 위해 사용된다.

값 추가와 삭제

값 추가

• 새 노드 추가: 완전 이진 트리의 성질을 유지하기 위해 힙의 가장 마지막 위치에 새 값을 추가한다.
• 힙 속성 복구
  • 새로 추가된 노드가 부모 노드보다 크다면, 두 노드를 교환한다.
  • 교환을 반복하면서 새 노드가 적절한 위치에 도달할 때까지 진행한다.
• 시간 복잡도
  • O(log n): 트리의 높이만큼 이동하며 비교 및 교환이 이루어지므로 높이가 로그 단위로 증가하는 힙에서는 O(log n) 시간이 소요된다.

예시

초기 힙

    10
   /  \
  9    8
 / \
3   4

새 값 15 추가

    10
   /  \
  9    8
 / \   /
3   4 15

15와 10 교환:

    15
   /  \
  10   8
 / \   /
3   4 9

값 삭제

• 힙에서 값 삭제는 일반적으로 루트 노드(최대값 또는 최소값)를 삭제한다.
• 루트 노드 교체: 힙의 마지막 노드를 루트로 이동시킨다.
• 힙 속성 복구
  • 루트 노드가 자식 노드보다 작다면, 더 큰 자식 노드와 교환한다.
  • 교환을 반복하며 루트 노드가 적절한 위치에 도달할 때까지 진행합니다.
• 시간 복잡도
  • O(log n): 트리의 높이만큼 이동하며 비교 및 교환이 이루어지므로 O(log n) 시간이 소요된다.

예시

초기 힙

    15
   /  \
  10   8
 / \   /
3   4 9

루트 노드 15 삭제
마지막 노드 9를 루트로 이동

    9
   /  \
  10   8
 / \
3   4

9와 10 교환

    10
   /  \
  9    8
 / \
3   4

코드로 살펴보기

import java.util.ArrayList;

public class MaxHeap {
    private ArrayList<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList<>();
    }

    // 값 삽입 
    public void insert(int value) {
        heap.add(value); 
        heapifyUp(heap.size() - 1);
    }

    // 루트 노드 삭제
    public int delete() {
        if (heap.size() == 0) {
            throw new IllegalStateException("Heap is empty");
        }

        if (heap.size() == 1) {
            return heap.remove(0);
        }

        int rootValue = heap.get(0);
        heap.set(0, heap.remove(heap.size() - 1)); // 마지막 노드를 루트로 이동
        heapifyDown(0); // Heapify-Down 
        return rootValue;
    }

    // Heapify-Up (삽입 시 호출)
    private void heapifyUp(int index) {
        int parentIndex = (index - 1) / 2;
        while (index > 0 && heap.get(index) > heap.get(parentIndex)) {
            swap(index, parentIndex); // 현재 노드와 부모 노드 교환
            index = parentIndex;
            parentIndex = (index - 1) / 2;
        }
    }

    // Heapify-Down (삭제 시 호출)
    private void heapifyDown(int index) {
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        int largest = index;

        // 왼쪽 자식 노드와 비교
        if (leftChildIndex < heap.size() && heap.get(leftChildIndex) > heap.get(largest)) {
            largest = leftChildIndex;
        }

        // 오른쪽 자식 노드와 비교
        if (rightChildIndex < heap.size() && heap.get(rightChildIndex) > heap.get(largest)) {
            largest = rightChildIndex;
        }

        // 부모와 자식 노드를 교환
        if (largest != index) {
            swap(index, largest);
            heapifyDown(largest); // 재귀
        }
    }

    // 두 노드의 값을 교환
    private void swap(int i, int j) {
        int temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
}