[알고리즘] 힙(Heap)

1. 힙(Heap)이란?

데이터에서 최대값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리(Complete Binary Tree)로

데이터의 삽입과 삭제가 빠르며 각각의 수행시간이 O(logN)이다.

 

힙을 사용하는 이유는? 🤔

• 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n) 이 걸림
• 이에 반해, 힙에 데이터를 넣고, 최대값과 최솟값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛) 이 걸림
• 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

 

Heap에서 할 수 있는 것은 이진 탐색 트리에서도 가능한데 힙을 쓰는 이유가 무엇일까? 🤔

• Heap으로 구현 가능한 것은 균형 이진트리에서도 가능 한것이 맞고, 시간복잡도도 O(logN)으로 동일함
• 그러나 Heap은 균형 이진 트리보다 수행 속도가 빠르고, 공간을 적게 차지함
• 그러므로 최소/ 최대 값의 확인 및 삭제가 필요할 때는 Heap을 사용하는 것이 더 좋음

 

힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임

• 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나(최대힙)/작거나(최소힙) 같다.
• 완전 이진트리 형태를 가짐

1) 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
2) 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
* 완전 이진트리 : 마지막 레벨을 제외하곤 완전히 꽉 찬 상태이고, 마지막 레벨의 맨 왼쪽부터 꽉 차 있어야함.

 

2. 힙의 구현

1) 힙의 삽입 연산

① 트리의 가장 마지막 위치에 노드를 삽입한다.

② 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.

③ 만족하지 않는다면 부모와 자식의 키 값을 바꾼다.

④ 조건에 만족하거나 추가된 노드가 루트에 도달할 때 까지 2~3을 반복한다.

 

2) 힙의 삭제 연산

① 힙의 삭제 연산은 항상 루트 노드를 삭제한다.

② 트리의 가장 마지막 노드를 루트 자리로 삽입한다.

③ 바꾼 위치의 노드가 힙 조건을 만족하는지 확인한다.

④ 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드와 키 값을 바꾼다.

⑤ 조건을 만족하거나 리프 노드에 도달할 때 까지 3~4를 반복한다.

 

3. 힙 선언

import java.util.PriorityQueue;

//오름차순 PriorityQueue 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//내림차순 PriorityQueue 선언
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

 

4. 관련 문제

[우선순위 큐] 백준 1927번 최소 힙(Java)

 

 

[참고 : https://seongry.github.io/2021/04-24-heap-01/ ]