🔷 힙 (Heap)이란?
힙 (Heap)은 우선순위 큐 (Priority Queue)를 구현하기 위한 자료구조이다.
완전 이진 트리를 기초로 하며, 최소 혹은 최대값을 찾기에 효율적이다.
힙은 반정렬 상태 (느슨한 정렬 상태)를 유지한다.
🔹우선순위 큐 (Priority Queue)
큐(Queue)는 가장 먼저 들어온 데이터가 가장 먼저 나가는 형식의 FIFO(First-In First-Out) 구조이다.
우선순위 큐(Priority Queue)는 먼저 들어온 데이터가 아닌, 우선순위가 가장 높은 데이터가 먼저 나가는 구조이다.
우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.
🔹힙의 특징
완전이진트리 형태로 이루어져 있다.
부모노드와 서브트리간 대소 관계가 성립된다. : 반정렬 상태
이진탐색트리(BST)와 달리 중복된 값이 허용된다.
🔷 힙의 종류
🔹최대 힙 (Max Heap)
key(부모노드) ≥ key(자식노드)
이진 힙의 구현 방식에서 최댓값을 찾기 위한 구조
부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리
루트 노드가 가장 큰 값
🔹최소 힙 (Min Heap)
key(부모노드) ≤ key(자식노드)
이진 힙의 구현 방식에서 최솟값을 찾기 위한 구조
부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리
루트 노드가 가장 작은 값
🔷 힙의 구현
힙은 일반적으로 배열로 구현한다.
완전 이진 트리 (complete binary tree)이므로 중간에 비어있는 요소가 없다.
🔹자식 노드 구하기
1. 왼쪽 자식 노드
index = (부모 index) * 2
2. 오른쪽 자식 노드
index = (부모 index) * 2 + 1
🔹부모 노드 구하기
부모 index = (자식 index) / 2
🔷 힙의 삽입
시간 복잡도 : O(logN)
🔹최대 힙
1. 가장 마지막 노드에 값을 삽입
2. 부모 노드와 비교
- 삽입 노드가 부모 노드보다 크면 부모 노드와 교환
- 모든 노드가 최대 힙을 만족할 때까지 진행 : 부모 노드 > 삽입 노드
🔹최소 힙
1. 가장 마지막 노드에 값을 삽입
2. 부모 노드와 비교
- 부모 노드보다 작으면 부모 노드와 교환,
- 모든 노드가 최소 힙을 만족할 때까지 진행 : 부모 노드 < 삽입 노드
🔷 힙의 삭제
시간 복잡도 : O(logN)
최대 | 최소 힙에서 최소, 최댓값을 구하는 경우 : O(1)
🔹최대 힙
1. 루트 노드 제거
2. 마지막 노드를 루트 노드로 삽입
3. 삽입 노드와 자식 노드 비교
- 삽입 노드가 부모 노드보다 크면 부모 노드와 교환
- 모든 노드가 최대 힙을 만족할 때까지 진행 : 부모 노드 > 삽입 노드
🔹최소 힙
1. 루트 노드 제거
2. 마지막 노드를 루트 노드로 삽입
3. 삽입 노드와 자식 노드 비교
- 부모 노드보다 작으면 부모 노드와 교환,
- 모든 노드가 최소 힙을 만족할 때까지 진행 : 부모 노드 < 삽입 노드
🔷 관련 포스트