힙 heap (미완)

heap

• 사용목적 : 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조
  (여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠름)
• 시간복잡도
  • 삭제 : $O(log_2n)$
  • 삽입 : $O(log_2n)$

• 특징
  • 완전이진트리 형태로 이루어져 있다.
  • 부모노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태)
  • 이진탐색트리(BST)와 달리 중복된 값이 허용된다.

레퍼런스

[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)