Heap

: 이진 트리에 있는 노드 중에서 가장 값이 큰 노드나 값이 가장 작은 노드를 찾기 위해 만든 자료구조

힙의 불변성

힙이 되기 위한 조건

1. 최대 / 최소 원소에 즉각적으로 접근이 가능해야 한다.

2. 부모 노드가 자식 노드보다 항상 크거나 작아야 한다.

연산

• 검색 및 읽기
  • 최대 / 최소 원소에 대해서만 가능하며 O(1)이다.
• 삽입
  • 완전 이진 트리이기 때문에 O(LogN)이다.
• 삭제
  • 최대 / 최소 원소에 대해서만 가능하며 O(LogN)이다.