HEAP(힙)

1. 힙: 힙 성질(heap property)을 만족하는 이진 트리

- 힙은 자식이 꽉꽉 채워져 있어야 한다. 

 

그렇다면 힙성질이란?

 

- 힙 성질: 모든 부모 노드의 key값은 자식 n노드의 key값 보다 작지 않다.

즉 부모님이 자식보다 더 크다!

그렇다면 root노드의 값이 가장 크다!

---

2.

트리를 표현하는 방법 중 리스트를 이용하여, 모든 노드를 빈 곳도 다 작성하는 방법 사용시 

- 단점: 메모리 낭비가 심하다.(비어있는 곳도 None으로 저장)

- 장점: 자식 노드와 부모 노드의 위치를 알 수 있다.

ex) H = [a, b, c, None, d, e, f] 일때, 

H[k]의 왼쪽 자식 노드 : H[k*2+1]

H[k]의 오른쪽 자식 노드 : H[k*2+2]

H[k]의 부모 노드 : H[(k-1)//2]

 

---

3. 

- 힙성질을 만족하기 위해서 리스트의 왼쪽 끝부터(leaf node) 차근차근 숫자를 내린다. 

- 트리를 힙성질을 만족하게 만들기 위해 --> make_heap, heapify_down을 실행

힙을 만드는 make힙과, hepify_down

insert연산과 delete_max연산

####HEAP과 관련된 여러 연산들

# 1, make_heap: O(n), O(nlogn)
# 2, insert: O(logn)
# 3, find_max: O(1) --> root node가 가장 큰 값임을 이미 안다
# 4, delete_max: O(logn)
# 5, heapify_down: O(h) = O(logn)
# 6, heapify_up: O(h) = O(logn)