힙이란 무엇일까?

<aside> 👉🏿 힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Complete Binary Tree)

힙은 트리 기반의 자료 구조이다.

</aside>

힙의 종류

<aside> 💡 이진 힙 Binray Heap - 자식 노드가 2개인 경우에는 이진 힙이라고 불린다.

최소 힙 - 부모 노드가 자식 노드보다 값이 작은 힙이다.

최대 힙 - 최소 힙과는 반대로 자식 노드가 항상 부모 노드보다 값이 작다.

</aside>

  8      Level 0
6   3    Level 1
 2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!

   8      Level 0
 6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 1     Level 2  # 자식 노드보다 크니까 **힙이 맞습니다!**

   8      Level 0
 6   **3**    Level 1  # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 **5**     Level 2  # 자식 노드보다 크지 않아서 **힙이 아닙니다..!**

힙에서 오해하기 쉬운 특징

<aside> 💡 힙은 정렬된 구조가 아니다. 최소힙의 경우 부모노드가 항상 작다라는 조건과 최대 힙의 경우 부모노드가 항상 크다라는 조건만 있을 뿐, 서로 정렬되어있지 않다.

예를들어 오른쪽 자식 노드가 레밸 차이에도 불구하고, 왼쪽 노드보다 더 작은 경우도 얼마든지 있을 수 있다

</aside>

힙 구현하기

최대 힙 - 삽입 알고리즘

<aside> 💡 1. 원소를 맨 마지막에 넣는다.

1. 그리고 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.
2. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2번 과정을 반복한다. </aside>

이 맥스 힙에서 9를 추가해보겠습니다!
      8      Level 0
    6   3    Level 1  
   4 2 1     Level 2 

1. 맨 마지막에 원소를 넣습니다.

      8      Level 0
    6   3    Level 1  
   4 2 1 **9**   Level 2 

2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.

      8      Level 0
    6   **3**    Level 1  
   4 2 1 **9**   Level 2 

      8      Level 0
    6   **9**    Level 1  
   4 2 1 **3**   Level 2 

2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.

      **8**      Level 0
    6   **9**    Level 1  
   4 2 1 3   Level 2 

      **9**      Level 0
    6   **8**    Level 1  
   4 2 1 3   Level 2 

3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다!

      **9**      Level 0
    6   **8**    Level 1  
   4 2 1 3   Level 2

최대 힙 - 삽입 시간 복잡도