힙(heap)

• 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 힙은 일종의 반정렬 상태를 유지함
• 힙 트리에서는 중복 값을 허용(이진 탐색 트리에서는 불허)

1. 최대 힙(Max heap): 오름차순 출력

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

2. 최소 힙(Min heap): 내림차순 출력

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