[자료구조] 힙(Heap) 자료구조 알아보기 & Java 예제 코드

자료구조 중 힙(Heap)에 대해 정리해보자.

---

 

힙(Heap)이란?

자료구조 중 힙(Heap)은 특정한 순서에 따라 정렬된 요소들을 저장하는 트리 기반의 자료구조이다.

Heap은 일반적으로 이진 힙(binary heap)으로 구현되며, 우선순위 큐(priority queue)와 같은 다른 추상 자료형의 구현에 주로 사용된다.

 

Heap은 다음과 같은 특징을 가지고 있다.

1. 완전 이진 트리(Complete Binary Tree) : Heap은 완전 이진 트리의 형태를 가진다. 이는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있는 형태를 말한다.
2. 부모-자식 노드 관계 : Heap의 부모 노드는 항상 자식 노드보다 우선순위가 높거나 같은 값을 가집니다. 이러한 특성은 최대 힙(max heap)에서는 부모 노드가 항상 자식 노드보다 큰 값을 가지며, 최소 힙(min heap)에서는 부모 노드가 항상 자식 노드보다 작은 값을 가지는 것을 의미한다.
3. 힙 속성 : Heap의 모든 부모-자식 쌍에 대해 특정한 조건을 만족해야 한다. 최대 힙에서는 모든 부모 노드가 자식 노드보다 크거나 같은 값을 가져야 하며, 최소 힙에서는 모든 부모 노드가 자식 노드보다 작거나 같은 값을 가져야 한다.

 

Heap은 주로 다음과 같은 연산을 지원한다.

1. 삽입(Insertion) : Heap에 새로운 요소를 추가한다. 일반적으로 우선순위 큐에서는 우선순위에 따라 요소가 삽입된다.
2. 삭제(Deletion) : Heap에서 가장 우선순위가 높은 요소를 삭제한다. 최대 힙에서는 가장 큰 요소가 삭제되고, 최소 힙에서는 가장 작은 요소가 삭제된다.

 

출처 :  https://ko.wikipedia.org/wiki/힙_(자료_구조)

1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다.

 

 

 

힙(Heap)의 장점 및 단점

장점

1. 빠른 삽입 및 삭제 : Heap은 특정한 순서에 따라 정렬된 상태를 유지하므로 삽입과 삭제 연산이 상수 시간(O(log n))에 이루어진다. 이는 요소들의 우선순위에 따라 빠르게 작업을 처리할 수 있다는 것을 의미한다.
2. 우선순위 기반 작업 처리 : Heap은 우선순위 큐와 같은 다른 추상 자료형을 구현하는 데 사용된다. 최대 힙인 경우에는 가장 큰 우선순위를 가진 요소에 빠르게 접근할 수 있고, 최소 힙인 경우에는 가장 작은 우선순위를 가진 요소에 빠르게 접근할 수 있다. 이를 통해 우선순위에 따라 작업을 관리하고 처리할 수 있다.

 

단점

1. 임의 접근의 어려움 : Heap은 일반적으로 완전 이진 트리의 형태를 가지며, 배열 또는 연결 리스트를 사용하여 구현된다. 이러한 구조는 임의 접근을 지원하지 않고, 요소에 접근하기 위해 순차적인 탐색을 수행해야 한다. 따라서 특정한 요소를 찾는 데에는 O(n)의 시간이 걸린다.
2. 정렬 유지의 오버헤드 : Heap은 정렬된 상태를 유지하기 위해 삽입과 삭제 연산 시에 정렬을 조정해야 한다. 이는 일정한 오버헤드를 발생시킬 수 있다. 따라서 요소들의 정렬 상태가 항상 필요하지 않은 경우에는 다른 자료구조를 고려하는 것이 좋다.
3. 배열로 구현 시 추가적인 공간 요구 : Heap은 일반적으로 배열 또는 연결 리스트를 사용해 구현된다. 배열 기반의 Heap에서는 공간을 미리 할당해야 하므로 요소의 개수에 따라 적절한 크기를 선택해야 하며, 요소의 개수에 따라 추가적인 공간을 필요로 한다.

 

힙(Heap)은 삽입 및 삭제 연산에 있어서 뛰어난 성능을 보이지만, 임의 접근과 정렬 유지에 관련된 한계가 있다.

 

 

 

Heap 예시 코드(Java)

Java에서는 PriorityQueue 클래스를 사용해 Heap을 구현할 수 있다.

PriorityQueue는 요소를 삽입할 때 Heap 속성을 유지하고, peek() 메소드를 통해 최소값에 접근하며, poll() 메소드를 통해 최소값을 삭제한다.

 

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // Integer를 저장하는 최소 힙 생성
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 요소 추가
        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);

        // 최소값 확인
        int minValue = minHeap.peek();
        System.out.println("Min value: " + minValue); // Min value: 1

        // 최소값 삭제
        int deletedValue = minHeap.poll();
        System.out.println("Deleted value: " + deletedValue); // Deleted value: 1

        // 최소값 확인
        minValue = minHeap.peek();
        System.out.println("Min value: " + minValue); // Min value: 2
    }
}