힙

힙(Heap)은 완전 이진트리에 있는 노드 중에서 값이 가장 큰 노드나 값이 가장 작은 노드를 찾이 위해 만든 자료구조이다.

• 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙
• 값이 가장 작은 노드를 찾기 위한 힙을 최소 힙

힙은 우선순의 큐 (Priority Queue)라고도 한다.
유니티에선 버전때문에 사용불가능하다. 따로 구현을 해야한다.

힙의 불변성

힙이 되기 위한 조건이 있다.

• 최대 / 최소 원소에 즉각적으로 접근이 가능해댜 한다

  • 그래서 최대 / 최소 원소는 항상 루트 노드에 존재한다.

• 부모 노드가 자식 노드보다 항상 크거나(Max Heap), 작아야한다(Min Heap)

  연산

• 검색 및 읽기

  • 최대 / 최소 원소에 대해서만 가능하며 O(1)이다.

• 삽입

  • 완전 이진 트리이기 때문에 O(logN)이다.

• 삭제

  • 최대 / 최소 원소에 대해서만 가능하며 O(logN)이다.