자료구조 - 힙(Heap)

Heap이란?

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조

Heap의 종류

최대 힙(max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• Key(부모 노드) >= key(자식 노드)

최소 힙(min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모 노드) <= key(자식 노드)
  

Heap 삽입

1. 힙에 새로운 요소가 들어오는 경우, 새로운 노드를 힙의 마지막 노드에 삽입
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족

ex) 최대 힙

Heap 삭제

이미지 출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html