Heap❓

Heap❓

• 완전 이진 트리 형태
• 최대, 최소 값을 빠르게 찾아내는데 유용한 자료구조
• 우선순위 큐(Priority Queue)와 같은 다른 추상 자료형의 구현에 주로 사용

Heap의 종류

1. 최소 힙 (Min Heap)
   • 루트노드가 최솟값이 되고, 부모노드의 key는 자식노드의 key보다 작아야 한다는 규칙
2. 최대 힙 (Max Heap)
   • 루트노드가 최댓값이 되고, 부모노드의 key가 자식 노드의 key보다 커야 한다는 규칙

Heap 장점 및 단점

장점

• 빠른 삽입과 삭제: Heap은 정렬된 상태를 유지하므로 삽입과 삭제 연산이 상수 시간(O(log n))에 이루어짐
• 우선순위 기반 처리: 최대 힙(Max Heap)의 경우에는 가장 큰 우선순위를 가진 요소에 빠르게 접근 가능, 최소 힙(Min Heap)의 경우에는 가장 작은 우선순위를 가진 요소에 빠르게 접근 가능

단점

• 임의 접근 어려움: Heap은 완전 이진 트리의 형태를 가지고, 배열 또는 연결 리스트를 사용하여 구현되므로 임의 접근을 지원하지 않음. 요소에 접근하기 위해 순차 탐색을 해야하므로 O(N)이 소요됨
• 정렬 유지의 오버헤드: Heap은 정렬된 상태를 유지해야 하므로 삽입 및 삭제 연산시 정렬을 위한 연산이 있어 오버헤드가 발생할 수 있음

 

시간복잡도

연산	시간복잡도
삽입	O(log N)
삭제	O(log N)

• 삽입 및 삭제 모두 최악의 경우의 교환 횟수는 Heap의 높이(height)
• Heap은 완전 이진 트리이므로 높이가 log2 N을 넘지 않기 때문

Index

• 구현의 용이를 위해 인덱스를 1부터 시작

1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2
2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1
3. 부모 노드 인덱스 = 자식 노드 인덱스 / 2

 

---

 

Priority Queue

• Heap의 대표적인 응용 사례
• 우선순위 큐로 데이터 중에서 우선순위가 높은 데이터를 빠르게 알 수 있다.
• 큐와 연산이 동일하나 우선순위가 가장 높은 데이터를 알 수 있어, 이를 통해 최대 힙과 최소 힙을 구현 가능
• 최대 값이 우선순위인 큐가 최대 힙, 최소 값이 우선순위인 큐가 최소 힙이 됨

Priority Queue 사용법

Priority Queue 선언

import java.util.PriorityQueue;

// 낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언 (Default)
PriorityQueue<Integer> pqLowest = new PriorityQueue<>();

// 높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> pqHighest = new PriorityQueue<>(Collections.reverseOrder());

 

Priority Queue 값 추가 및 변경

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.add(1);            // pq에 1 추가
pq.offer(2);        // pq에 2 추가

 

Priority Queue 값 삭제

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.poll();            // 헤드 값 반환 및 제거, pq가 비어있을 경우 Null 반환
pq.remove();        // 헤드 제거, pq가 비어있을 경우 예외 발생

pq.clear();            // pq에 저장되어 있는 모든 값 삭제

 

Priority Queue 값 조회

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.peek();            // 헤드 값 반환, pq가 비어있을 경우 Null 반환
pq.element();        // 헤드 값 반환, pq가 비어있을 경우 예외 발생

 

---

 

Reference

https://hoehen-flug.tistory.com/32
https://innovation123.tistory.com/111
https://velog.velcdn.com/images/suk13574/post/45ecd7ec-1a95-45c8-8aab-10e6fd3abc54/image.jpg
https://st-lab.tistory.com/205