힙(heap)

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

1 개요[ | ]

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

2 우선순위큐와의 관계[ | ]

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

3 같이 보기[ | ]

4 참고[ | ]

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}