자료구조 힙(Heap)이란?

오늘은 힙(heap)에 대해서 알아볼 생각이다. 

힙은 데이터에서 가장 큰(또는 가장 작은) 항목에 빠르게 접근하도록 설계된 트리 기반의 자료 구조이다. 

데이터 정렬 , 우선순위 큐 등 다양한 알고리즘에서 활용된다.

 

By Ermishin - 자작, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=12251273

 

 

 

힙(heap)이란?

힙은 '완전 이진 트리(complete binary tree)'의 한 종류로, 힙에 저장된 각 노드의 키(key)는 자식 노드의 키와 비교하여 특정 순서를 유지한다. 힙에는 두가지 유형이 있다.

 

• 최대 힙(Max Heap): 부모 노드의 키가 자식 노드의 키보다 항상 크거나 같다. 따라서 힙의 루트(root)는 항상 가장 큰 키를 가진 노드이다. 
• 최소 힙(Min Heap): 부모 노드의 키가 자식 노드의 키보다 항상 작거나 같다. 이 경우, 루트는 항상 가장 작은 키를 가진 노드이다.

 

 

힙(heap)의 특징

1. 최대/최소 원소의 접근 : 힙은 가장 큰값 또는 작은 값을 상수 시간 O(1)에 접근할 수 있다. 
2. 삽입과 삭제 연산의 효율 : 삽입 연산은 보통 O(logN)의 시간 복잡도를 가지고 삭제 연산도 O(log N)의 시간 복잡도를 가진다. 이는 힙의 특성을 유지하기 위해 트리를 재조정 해야되기 때문이다.
3. 정렬되지 않은 상태 유지 : 힙은 일반적으로 정렬되지 않은 상태를 유지한다. 최대/최소 원소에 접근하는 것이 주된 목적이다. 

힙은 주로 우선순위 큐(Priority Queue), 힙 정렬(Heap Sort), 다익스트라 알고리즘(Dijkstra's Algorithm)등의 알고리즘에서 활용되는 중요한 자료구조이다.

 

 

 

---

 

 

힙의 장/단점

장점

1. 효율성 : 힙은 우선순위 큐를 구현하는데 가장 효율적인 자료구조이다. 왜냐하면 최댓값 또는 최솟값을 빠르게 찾을 수 있기 때문이다. 이러한 속성은 데이터 스트리밍, 그래프 알고리즘 등에서 효율적인 성능을 발휘한다.
2. 복잡도 : 힙에서의 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가진다. 이는 힙이 항상 균형을 유지하기 때문이다.
3. 플렉서블성 : 힙은 최대 힙과 최소 힙이라는 두 가지 다른 형태를 가질 수 있다. 

 

 

단점

1. 정렬 : 힙은 우선순위에 따라 데이터를 정렬하지만, 동일한 우선순위를 가진 항목 간에는 순서를 보장하지 않는다 (즉, 힙은 정렬된 구조가 아니다) 
2. 공간 복잡성 : 힙 구조를 유지하려면 부가적인 정보가 필요하고 이로 인해 추가 메모리를 필요로 한다.
3. 복잡성 : 힙은 구현이 비교적 복잡하고, 초기 구현자에게는 알고리즘이 어려울 수 있다.
4. 일관성 : 부모-자식 관계에서 일관성을 유지하려면 힙의 노드를 계속 업데이트해야한다. 이는 추가적인 연산이 필요하다

-참고자료- 

2023.07.11 - [➜ Java] - 큐(Queue)란 / 큐의 메서드 정리 (feat. 우선순위 큐)

큐(Queue)란 / 큐의 메서드 정리 (feat. 우선순위 큐)

여기에 우선순위 큐를 정렬한 부분을 보면 알 수 있다.

 

 

---

힙(heap)의 삽입

1. 초기 힙 :

2. '8' 이라는 값 삽입

 

 

3. 부모 노드 7 보다 8이 더 크므로 교환

4. 부모 노드 10 보다 8이 작으므로 더 이상 교환하지 않는다.

 

 

 

---

 

힙(heap) 삭제

1. 초기 힙:

 

2. 루트 노드'10'삭제시 가장 오른쪽 하단 노드 '4' 가 루트 노드가 된다

3. 루트 노드 '4'와 그 자식들을 비교하여 힙 속성을 유지하도록 노드를 교환한다. '4'는 자식 노드 ' 9'와 '8'보다 작으므로, 가장 큰 자식 노드인 '9'와 교환한다

4. 또 비교하고 7과 교환하도록 한다

 

이런식으로 힙의 속성을 유지하면서 노드 삭제 작업이 이루어진다.

 

 

---

힙의 구현

-최대 힙(Max Heap)

class MaxHeap {
    int[] heap;  // 힙을 나타내는 배열
    int size;  // 현재 힙의 크기

    // 생성자 : 힙의 용량(capacity)을 입력으로 받음
    public MaxHeap(int capacity) {
        heap = new int[capacity + 1];  // 1-based index를 사용하기 위해 배열의 크기를 capacity+1로 설정
        size = 0;  // 초기 힙의 크기는 0
    }

    // 삽입 함수
    public void insert(int value) {
        heap[++size] = value;  // 새로운 값을 힙의 마지막 요소 다음에 삽입

        // 새로 삽입된 요소를 부모노드들과 비교하며 최대 힙의 조건을 만족할 때까지 위로 이동(sift up)
        for (int i = size; i > 1; i /= 2) {
            if (heap[i] > heap[i / 2]) {
                swap(i, i / 2);
            } else {
                break;
            }
        }
    }

    // 삭제 함수 (힙에서 가장 큰 값 삭제)
    public int delete() {
        if (size == 0) throw new RuntimeException("The heap is empty!");  // 힙이 비어있을 경우 예외 발생

        int max = heap[1];  // root 노드 값을 저장 (최대값)
        heap[1] = heap[size--];  // 마지막 노드를 root로 이동
        
        // root 노드를 자식노드들과 비교하며 최대 힙의 조건을 만족할 때까지 아래로 이동(sift down)
        for (int i = 1; i * 2 <= size;) {
            int largerChild;
            // 자식노드 중 더 큰 노드를 선택
            if (i * 2 + 1 <= size) {
                largerChild = heap[i * 2] > heap[i * 2 + 1] ? i * 2 : i * 2 + 1;
            } else {
                largerChild = i * 2;
            }

            // 부모노드가 자식노드보다 크다면, 최대 힙의 조건 만족 -> 반복 종료
            if (heap[i] > heap[largerChild]) {
                break;
            }

            swap(i, largerChild);  // 부모노드와 자식노드 swap
            i = largerChild;  // 부모노드가 자식노드로 이동
        }

        return max;  // 삭제된 root 노드 값(최대값) 반환
    }

    // 두 인덱스의 값을 바꾸는 helper 함수
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}