[Algorithm] Heap

Heap

• 완전 이진트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
• 루트 노드가 가장 큰 최대 힙과 가장 작은 최소 힙이 존재한다

삽입

1. 완전 이진트리에 속하도록 마지막에 새로운 노드를 생성한다
2. 부모 노드와 값을 비교해 최대/최소에 맞게 자리를 변경을 반복한다

삭제

1. 루트 노드의 원소를 삭제한다
2. 가장 마지막에 위치한 노드를 루트로 옮긴다
3. 자식 노드와 값을 비교해 최대/최소에 맞게 자리를 변경한다