[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
            }
        });
    }
}