힙 Heap

• 항상 완전 이진 트리 형태
  -> 중복을 허용
  -> 반 정렬 상태임 [= 부모 자식관계에선 정렬되어있지만, 형제끼리는 정렬되어있지않음]

• 최소값, 최대값을 빠르게 찾는데 유용
  -> 최소힙 Min Heap , 최대힙 Max Heap
  -> 최소힙 : 부모 노드의 키 ≤ 자식 노드의 키
  -> 최대힙 : 부모 노드의 키 ≥ 자식 노드의 키

• Heap의 특성(같은 레벨에선 노드가 좌측부터 채워짐)으로 인해 보통 배열을 통해서 구현한다.

Heap의 삽입

Min Heap을 예시로 함

1. 트리의 가장 끝에 데이터 삽입
2. 부모 노드와 키를 비교한 후 삽입된 키가 더 작을 경우 부모와 교체 (반복)

Heap의 삭제

Min Heap을 예시로 함

1. 항상 최상위 노드를 반환 & 삭제
2. 가장 마지막 위치의 노드를 최상위로 옮김
3. 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 교체