힙

우선순위 큐를 구현할 때 사용하는 대표적인 자료구조이다.

• Max, Min 값 탐색에 가장 효율적인 방법이다.
  -> 특정 키의 우선순위 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조
• 느슨한 정렬을 유지한다.

우선순위 큐 구현 방법

1. 리스트를 이용한 구현
   • 시간복잡도
     • 삽입 O(1) : 단순히 리스트 후단에 삽입하는 작업
     • 삭제 O(n) : 정렬되지 않은 배열의 순차탐색의 선형적 시간복잡도를 따라
2. 힙을 이용한 구현
   • 시간복잡도
     힙으로의 N개의 데이터 삽입/삭제 작업은 그 자체로 힙 정렬과 동일하다.
     따라서 N개의 데이터를 대상으로 하는 삽입/삭제의 시간복잡도는 O(NlogN)을 소요한다.
     
     
     • 삽입 O(logN)
     • 삭제 O(logN)

힙 속성 ( heap property )

설명1.

1. heap order property

Max Heap -> 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다.
Min Heap -> 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다.

2. heap shape property

힙 트리는 완전이진트리의 모양으로, 마지막 레벨의 모든 노드는 왼쪽으로 쏠려있다.

설명2.

1. 힙은 '완전 이진 트리 (Complete Binary Tree)' 자료구조의 일종이다.
   

    완전이진트리? 
    
    	Full Binary Tree의 이름 그대로, 존재하는 노드들이 L->R 의 순서를 맞춰 빼곡히 채워져 나가는중인 트리.
    	+트리의 높이를 h라고 할 때, h-1의 높이까지는 포화이진트리의 상태로 모두 채워져 있어야 한다.
    

2. 힙에서는 항상 '루트 노드'를 제거한다.

3. 최소 힙 (min heap)
   - 루트 노드가 가장 작은 값을 가진다.
   -> 2의 루트노드 삭제 규칙에 따라, 가장 작은 값이 우선적으로 제거된다.

   최대 힙 (max heap)
   - 루트 노드가 가장 큰 값을 가진다.
   -> 2의 루트노드 삭제 규칙에 따라, 가장 큰 값이 우선적으로 제거된다.
   

Heapify

두 개의 서브 트리가

힙 트리 구성하기

힙 정렬

---

ref : https://www.youtube.com/watch?v=AjFlp951nz0