[TIL] 최소힙, 최대힙에 관해...

1️⃣ 힙이란 몰까...

• 힙은 완전이진트리다

- 부모노드의 인덱스 = (자식노드의 인덱스) // 2
- 왼쪽 자식노드의 인덱스 = (부모노드의 인덱스) * 2
- 오른쪽 자식노드의 인덱스 = (부모노드의 인덱스 * 2 +1

• 최대힙(내림차순)과 최소힙(오름차순)이 있다.
• 중복을 허용한다.

완전이진트리란

• 트리 왼쪽부터 채워지는 트리!!
  
  (출처 : https://www.programiz.com/dsa/complete-binary-tree)

힙을 쓰는 이유

• 시간복잡도가 O(nlogn)

2️⃣ 힙의 정렬 과정

1. 힙의 push 과정 (최소힙)

1. 뉴비가 들어온다. 이 때 뉴비는 가장 아래 레벨에 안착한다.
2. 뉴비와 뉴비의 부모노드를 비교한다. 이 때 뉴비가 더 작으면 부모<->뉴비 swap
3. 부모노드와 비교했을 때, 부모노드가 더 작거나, 최상위까지 갈 때까지 킵고잉

2. 힙의 pop 과정

1. 젤 상단 부모 노드를 냅다 pop한다. (이미 정렬되어있는 상태이기 때문)
2. 빈 상단 노드 자리에 가장 꼴찌 노드를 데려다놓는다.
3. 꼴찌노드와 자식 노드를 비교한다. 꼴찌노드가 둘보다 작으면 상단 유지
   3-1) 두 자식 모두 꼴찌보다 작을 경우, 왼/오 자식 노드를 비교해 더 작은 애를 현재 부모노드에 있는 꼴찌노드와 swap
   3-2) 두 자식 중 하나만 꼴찌보다 작을 경우 걔와 swap

3️⃣ 이 글을 쓰게 된 계기

https://school.programmers.co.kr/learn/courses/30/lessons/42628#

• 이 문제는 최소힙, 최대힙을 둘 다 써서 풀 수 있다. 남은 리스트를 출력하는 것이 answer인데 이 때, 힙에 남은 원소가 2개 초과이면 그 중 최소, 최대 두 개만 응답해야한다.
• 그래서 그냥 최소힙만 써서 답하자~ 하고 최소힙[0], 최소힙[-1] 요렇게 답을 했더니 한 테케에서만 틀리지않는가?!
• 질문하기를 보다가 머리를 띵 쳤도다.

  ```
  heap 에서 맨마지막 요소를 pop 하기위해 그냥 pop 하신것같은데, 
  아마 데이터 케이스가 적어서 정답처리가 된 것 같습니다. 
  힙에서 맨마지막 트리 높이의 맨마지막 요소가, 최솟값 이라는 보장이 없습니다
  ```

  허어억. 그렇다. 힙은 최대/최소만 보장하지 정렬을 해주진 않는다!!!
  따라서 힙에 push했다고 그대로 갔다쓰면 안되고, 정렬된채로 뽑고 싶다면 매번 heappop을 해줘야한다.

파이썬에서의 최대,최소힙

• heap 모듈의 힙은 기본으로 최소힙! 오름차순 정렬임.
• 출력 방법

from heap import heappop, heappush
## 최소힙
heap=[]
heappush(heap,1)
heappush(heap, 100)
heappush(heap,3)

nowmin = heappop(heap)

## 최대힙 - 음수로 넣고 빼면 된다.
maxheap=[]
heappush(maxheap,-1)
heappush(maxheap, -100)
heappush(maxheap,-3)

nowmax = -heappop(heap)

• PriorityQueue 모듈을 써도 되지만, 스레드의 안전을 요구하는 상황에서는 PriorityQueue, 아니라면 heapq를 사용하는 것이 좋다.
  즉, heapq 속도가 더 빠르다. 따라서 코딩 테스트의 경우 PriorityQueue를 사용하는 것보단 heapq를 사용하자!!!!!!!!!!