[자료 구조][Java] 힙 Heap

출처

ChatGPT

---

힙(Heap) 자료구조는 완전 이진 트리(Complete Binary Tree)의 한 형태로, 우선순위 큐(Priority Queue)를 구현하는 데 주로 사용되는 효율적인 자료구조이다. 힙은 요소들의 우선순위를 기반으로 빠르게 최대값이나 최소값을 찾고, 삽입 및 삭제 작업을 효율적으로 수행할 수 있도록 설계되었다.

• 관련 글 -> [자료 구조] 이진 트리 Binary Tree

 

1. 힙의 주요 특징

완전 이진 트리

힙은 모든 레벨이 완전히 채워져 있으며, 마지막 레벨도 왼쪽부터 채워져 있는 이진 트리이다. 이 특성 덕분에 힙은 배열(Array)로 효율적으로 구현될 수 있다.

힙 속성 Heap Property

최대 힙 Max-Heap

부모 노드의 값이 자식 노드의 값보다 크거나 같은 구조이다. 따라서 루트 노드는 힙에서 가장 큰 값을 가진다.

최소 힙 Min-Heap

부모 노드의 값이 자식 노드의 값보다 작거나 같은 구조이다. 따라서 루트 노드는 힙에서 가장 작은 값을 가진다.

효율적인 접근

힙은 루트 노드에서 최대값 또는 최소값이 위치하기 때문에, 최댓값 또는 최솟값을 O(1) 시간에 접근할 수 있다.

 

2. 힙의 구현 방법

힙은 일반적으로  배열(Array)을 이용해 구현된다. 배열을 사용해 힙을 구현하면 트리의 부모-자식 관계를 배열의 인덱스를 통해 쉽게 관리할 수 있다.

1. 배열을 이용한 힙 구현

노드 간의 관계

• 부모 노드 인덱스 : (i - 1) / 2
• 왼쪽 자식 노드 인덱스 : 2 * i + 1
• 오른쪽 자식 노드 인덱스 : 2 * i + 2

예시

// 배열을 이용한 최대 힙 예시
int[] heap = {50, 30, 20, 15, 10, 8, 16};

2. 객체를 이용한 힙 구현

객체를 사용해 힙을 구현할 수도 있으며, 각 노드는 다음과 같은 속성을 가진다.

• 값 Value : 노드의 데이터
• 왼쪽 자식 Left Child
• 오른쪽 자식 Right Child
• 부모 노드 Parent

class HeapNode {
    int value;
    HeapNode left;
    HeapNode right;
    HeapNode parent;

    HeapNode(int value) {
        this.value = value;
    }
}

 

3. 힙의 주요 연산

1. 삽입 Insertion

새로운 원소를 힙에 추가한다.

1. 새 노드를 힙의 마지막 위치에 삽입한다.
2. 힙 속성을 유지하기 위해 힙 업(Heap Up) 연산을 수행한다.
   • 추가한 노드와 부모 노드와 비교해 필요 시 위치를 교환한다. 
   • 최대 힙의 경우, 부모 노드보다 크면 교환한다.
   • 최소 힙의 경우, 부모 노드보다 작으면 교환한다.
   • 이 과정을 루트까지 반복한다.

• 힙 업 Heap Up : 힙에 새로운 요소를 삽입할 때 해당 요소가 부모 노드보다 작거나 크면(최소 힙 또는 최대 힙에 따라) 부모와 위치 교환(swap)을 하면서 위로 이동하는 과정이다. 이 과정은 트리의 루트 노드에 도달하거나 힙 속성이 유지될 때까지 계속된다.

시간 복잡도 : O(log n)

 

구현 예시 : 최대 힙

public void insert(int value) {
    // 배열의 다음 빈 공간에 값 삽입
    heap[size] = value;
    size++;

    // 힙 업
    int current = size - 1;
    while (current > 0) {
        int parent = (current - 1) / 2;
        if (heap[current] > heap[parent]) { // 최대 힙 기준
            // 교환
            int temp = heap[current];
            heap[current] = heap[parent];
            heap[parent] = temp;
            current = parent;
        } else {
            break;
        }
    }
}

 

예시 (최대 힙에  25 삽입)

초기 힙:
      20
     /  \
   15    18
  /  \   /
 10   12 17

1. 25를 마지막 위치에 추가:
      20
     /  \
   15    18
  /  \   / \
 10   12 17 25

2. 부모와 비교하여 상향 이동:
- 25 > 18이므로 교환
      20
     /  \
   15    25
  /  \   / \
 10   12 17 18
 
- 25 > 20이므로 교환
      25
     /  \
   15    20
  /  \   / \
 10   12 17 18
 - 최종 최대 힙 완료

 

2. 삭제 Deletion

최대 힙에서는 가장 큰 값을, 최소 힙에서는 가장 작은 값을 제거하는 연산

1. 루트 노드(가장 큰 값 또는 가장 작은 값)를 제거한다.
2. 힙의 마지막 노드를 루트로 이동시킨다.
3. 힙 다운(Heap Down) 연산을 통해 힙 속성을 유지한다.
   • 부모 노드를 자식 노드와 비교해 필요 시 위치를 교환한다.
   • 최대 힙의 경우, 자식 노드 중 더 큰 값과 교환한다.
   • 최소 힙의 경우, 자식 노드 중 더 작은 값과 교환한다.

• 힙 다운 Heap Down : 힙에서 루트 노드의 값을 삭제한 후, 힙의 속성(최대 힙 또는 최소 힙 속성)을 유지하기 위해 자식 노드와 비교하면서 아래로 이동시키는 과정

시간 복잡도 : O(log n)

 

구현 예시 : 최대 힙

public int remove() {
    if (size == 0) throw new NoSuchElementException("Heap is empty");

    int root = heap[0];
    heap[0] = heap[size - 1];
    size--;

    // 힙 다운
    int current = 0;
    while (current < size) {
        int left = 2 * current + 1;
        int right = 2 * current + 2;
        int largest = current;

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != current) {
            // 교환
            int temp = heap[current];
            heap[current] = heap[largest];
            heap[largest] = temp;
            current = largest;
        } else {
            break;
        }
    }

    return root;
}

 

예시 (최소 힙에서 삭제)

초기 힙 :
      2
     / \
    3   4
   / \
  7   6

1. 루트 노드 제거
(2 삭제)

2. 마지막 원소를 루트로 이동
      6
     / \
    3   4
   /
  7
  
  3. 자식과 비교해 하향 이동
  - 6 < 3이므로 교환
      3
     / \
    6   4
   /
  7
  -최소 힙 최종 완료

3. 찾기 Search

• 최대 힙에서 최댓값 찾기 : O(1)
• 최소 힙에서 최솟값 찾기 : O(1)
• 일반적인 값 찾기 : O(n)
  • 힙 전체를 순차적으로 탐색해야 한다. 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 방식을 사용한다.

 

4. 힙의 구현 예시

자바에서 배열을 이용한 힙의 구현

import java.util.Arrays;

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

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    // 부모 노드 인덱스
    private int getParentIndex(int index) { return (index - 1) / 2; }
    
    // 왼쪽 자식 노드 인덱스
    private int getLeftChildIndex(int index) { return 2 * index + 1; }
    
    // 오른쪽 자식 노드 인덱스
    private int getRightChildIndex(int index) { return 2 * index + 2; }

    // 삽입 연산
    public void insert(int value) {
        if (size == capacity) throw new IllegalStateException("Heap is full");

        heap[size] = value;
        size++;
        heapifyUp(size - 1);  // 힙 속성 유지 (상향식 정렬)
    }

    // 힙 정렬 (상향식)
    private void heapifyUp(int index) {
        while (index > 0 && heap[index] < heap[getParentIndex(index)]) {
            swap(index, getParentIndex(index));
            index = getParentIndex(index);
        }
    }

    // 최솟값(루트) 삭제
    public int removeMin() {
        if (size == 0) throw new IllegalStateException("Heap is empty");

        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);  // 힙 속성 유지 (하향식 정렬)
        return min;
    }

    // 힙 정렬 (하향식)
    private void heapifyDown(int index) {
        int smallest = index;
        int left = getLeftChildIndex(index);
        int right = getRightChildIndex(index);

        if (left < size && heap[left] < heap[smallest]) {
            smallest = left;
        }

        if (right < size && heap[right] < heap[smallest]) {
            smallest = right;
        }

        if (smallest != index) {
            swap(index, smallest);
            heapifyDown(smallest);
        }
    }

    // 두 요소 교환
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 힙 내용 출력
    public void printHeap() {
        System.out.println(Arrays.toString(Arrays.copyOfRange(heap, 0, size)));
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        minHeap.insert(20);
        minHeap.insert(15);
        minHeap.insert(30);
        minHeap.insert(5);
        minHeap.insert(10);

        minHeap.printHeap();  // [5, 10, 30, 20, 15]

        System.out.println("Min value removed: " + minHeap.removeMin());  // 5
        minHeap.printHeap();  // [10, 15, 30, 20]
    }
}

 

5. 힙의 응용

힙은 여러 알고리즘에서 중요한 역할을 하며, 다양한 응용 사례가 있다.

1. 우선순위 큐 Priority Queue

힙 자료구조는 우선순위 큐(Priority Queue)를 구현하는 데 많이 사용된다. 유선순위 큐에서는 요소가 들어온 순서가 아니라 우선순위에 따라 처리되며, 힙은 최댓값 또는 최솟값을 효율적으로 관리하는 데 유리하다.

자바에서는 PriorityQueue 클래스를 통해 최소 힙 기반의 우선수위 큐를 제공한다. 기본적으로 오름차순으로 동작하며, 사용자가 정의한 우선순위로 정렬할 수 있다.

2. 힙 정렬 Heap Sort

힙 정렬(Heap Sort)은 힙 자료구조를 이용한 정렬 알고리즘으로, 최대 힙이나 최소 힙을 구성한 후, 루트 노드를 제거하고 재정렬하는 과정을 반복해 정렬을 수행한다.

• 힙 정렬의 시간 복잡도는 O(log n)으로, 비교 기반 정렬 알고리즘 중 효율적인 편이다.
• 제자리 정렬(in-place sorting)이 가능하지만, 안정적인 정렬(stable sorting)은 아니다.

• 관련 글 -> [알고리즘] 제자리 정렬 In-Place Sorting
• 관련 글 -> [알고리즘] 안정적인 정렬 Stable Sorting

3. 다익스트라 알고리즘 Dijkstra's Algorithm

다익스트라 알고리즘은 최단 경로 알고리즘 중 하나로, 우선순위 큐를 사용해 가중치가 있는 그래프에서 최단 경로를 찾는다. 이 과정에서 최소 힙이 사용되어, 현재까지 가장 작은 거리를 가진 정점을 효율적으로 선택할 수 있다.

4. 이진 힙(Binary Heap)과 페어링 힙(Pairing Heap)

힙의 여러 변형 중 하나인 이진 힙과 페어링 힙은 각기 다른 특징과 장점을 가지고 있으며, 이진 힙은 가장 기본적인 형태이고, 페어링 힙은 더 복잡하지만 삽입과 삭제가 더욱 효율적이다.