힙(heap)

  다른 뜻에 대해서는 힙(hip) 문서를 참조하십시오.

  다른 뜻에 대해서는 힙(heap) 문서를 참조하십시오.

1 개요

heap

힙

• 완전 이진 트리의 하나
• 최대값, 최소값 탐색을 빠르게 하기 위해 고안된 완전이진트리 자료구조
• 주로 두 가지 유형: 최대 힙(max heap), 최소 힙(min heap)
  • 최대 힙에서는 부모 노드가 항상 자식 노드보다 크거나 같다.
  • 최소 힙에서는 부모 노드가 항상 자식 노드보다 작거나 같다.
  • 이러한 속성 덕분에 힙은 최대값이나 최소값을 빠르게 찾을 수 있다.
• 힙은 주로 배열을 사용하여 구현된다.

2 우선순위큐와의 관계

• 힙은 우선순위 큐를 구현하는 데 매우 효율적인 방법 중 하나이다.
• 힙을 사용하면 (우선순위에 따른) 삽입과 삭제 작업을 O(log n) 시간 안에 수행할 수 있다.
• 힙을 사용한 우선순위 큐 구현은 우선순위 변경이 자주 일어나는 대규모 데이터셋에 특히 유용하다.

3 같이 보기

• 트리
• 힙정렬
• 우선순위큐
• 완전이진트리

4 참고

• 위키백과 "힙 (자료 구조)"