[JAVA] 자료구조 Heap & Heap sort (힙 & 힙 정렬) + 구현
Heap 자료구조 란?
- 데이터에서 최댓값 과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리
시간 복잡도 : O(logN)
이진 트리의 개념
- node : 각각의 값을 노드라고 부름
- root : 뿌리 노드, 레벨 0, 가장 최상단 노드로 부모 노드가 존재하지 않는 노드
- parent node : 부모 노드, 아래에 자식 노드를 가지고 있는 노드
- child node : 부모 노드로 뻗어나온 하위 노드
- 완전 이진 트리의 일종으로, 왼쪽으로부터 자료구조를 채워나가는 형태
- 오른쪽은 비어있는 경우가 있을 수 있음
- 1차원 배열로 나타낼 수 있음 -> 정렬이 가능한 이유
- 배열로 구현 시에, 인덱스 1로 시작하는 것으로 구현하면 편리함 (0으로 시작해도 무관)
- 중복 값 허용
<인덱스 1로 시작하는 경우>
- (부모 노드의 인덱스) = (자식 노드 인덱스) / 2
- (왼쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2
- (오른쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2 + 1
<인덱스 0 으로 시작하는 경우>
- 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2
- 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1
- 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 2
Heap 종류
1. 최대(Max) 힙 : 부모 노드가 자식 노드 보다 큰 값을 갖는 경우
2. 최소(Min) 힙 : 자식 노드가 부모 노드 보다 큰 값을 갖는 경우
Heap Sort (힙 정렬)
아래의 완전 이진 트리 형태를 최대 힙 구조로 만드는 정렬 방법을 통해 설명
- 총 노드의 수 : 6 개
- 가장 오른쪽 아래에 위치한 부모 노드 구하기 : (마지막 노드 인덱스) / 2 = 3
1. 가장 오른쪽 아래에 위치한 부모 노드 - 자식 노드 간의 관계부터 최대 힙 구조를 이루는 지 확인
2. 3번 노드의 자식 노드는 하나 뿐이므로 자식 노드와 비교하여 부모 노드가 작다면 자리를 바꿈
-> 힙 구조를 이루게 됨
3. 부모 노드와 동일한 선상의 좌측 부모 노드로 이동해서 힙 구조를 이루는지 확인
4. 2번 노드의 자식 노드 중 더 큰 값을 찾아 부모 노드와 대조하여 자식 노드의 값이 크다면 자리를 바꿈
-> 힙 구조를 이루게 됨
5. 가장 좌측 부모 노드까지 확인을 했다면, 2번 노드와 3번 노드 즉, 부모 노드 역할을 했던 노드들의 부모 노드로 올라가 힙 구조를 이루는지 확인
6. 자식 노드들의 값을 비교하여 큰 값을 부모 노드와 대조하여 자식 노드의 값이 크다면 자리를 바꿈
-> 힙 구조를 이루게 됨
7. 루트 노드까지 완료되었다면 다시 한 번, 처음 시작했던 최하위 부모노드로 돌아가 다시 한 번 확인
-> 최대 힙 구조를 만족하도록 반복
-> 단, 루트 노드는 처음 정렬을 수행하게 되면 최대 값을 가지게 되므로 루트 노드를 제외하고 반복
-> 또한, 말단 노드의 경우는
8. 최대 힙 구조를 만족하는지 반복하여 검사
-> 만약 한 번이라도 swap(스왑, 자리 바꿈)이 발생했다면 다시 최대 힙 구조를 만족하는지 확인
9. 스왑이 일어나지 않고 검사를 통해 최대 힙 구조가 만족이 되면 검사를 멈춤 = 최대 힙 정렬 완료
-> 아래와 같이 최대 힙 정렬 구조로 정렬이 된 것을 확인
Heap 의 추가 , 삭제
*추후 보완 예정*
JAVA 로 최대 힙 정렬 구현
PriorityQueue(우선순위 큐) 를 사용하여 풀이가 가능
PriorityQueue를 사용하면 힙 정렬 알고리즘 풀이가 가능하다.
힙 정렬은 최소 힙 / 최대 힙 으로 정렬을 하는 방법이 있지만,
우선순위 큐의 경우에는 우선순위에 따라서 출력을 한다는 차이점이 존재한다.
java.util.PriorityQueue 의 경우, 일반적인 Queue 와 사용법이 거의 유사
import java.util.PriorityQueue;
import java.util.Collections;
class Main{
public void main(String[] args){
// 생성 - 제네릭에는 객체타입을 넣음
PriorityQueue<Object> pq = new PriorityQueue<>();
// 사용
pq.size(); // 우선순위 큐 안에 들어있는 요소 수 확인
pq.add(parameter); // 우선순위 큐 안에 요소 제공
pq.offer(parameter); // 우선순위 큐 안에 요소 제공
pq.peek(); // 우선 순위에 따른 가장 처음 반환 하는 요소를 꺼내지 않고 확인
pq.poll(); // 우선 순위에 따른 가장 처음 반환 하는 요소를 꺼내어 확인 & 제거
// PriorityQueue 의 경우 기본적으로 오름차순으로 정렬
// 다른 순서로 정렬을 원할 경우
// 1. Integer 의 경우 Collections 를 이용해 내림차순 정렬 가능
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
// 2. Comparator 이용하여 compare 메소드를 Override 해서 원하는 기준으로 정렬 가능
PriorityQueue<int[]> pq3 = new PriorityQueue<>(new Comparator<int[]>(){
@Override
public int compare(int[] o1, int[] o2){
// 정렬할 기준 입력
return
}
});
}
}