1 개요[ | ]
- heap
- 힙
- 완전 이진 트리의 하나
- 최대값, 최소값 탐색을 빠르게 하기 위해 고안된 완전이진트리 자료구조
- 주로 두 가지 유형: 최대 힙(max heap), 최소 힙(min heap)
- 최대 힙에서는 부모 노드가 항상 자식 노드보다 크거나 같다.
- 최소 힙에서는 부모 노드가 항상 자식 노드보다 작거나 같다.
- 이러한 속성 덕분에 힙은 최대값이나 최소값을 빠르게 찾을 수 있다.
- 힙은 주로 배열을 사용하여 구현된다.
2 우선순위큐와의 관계[ | ]
- 힙은 우선순위 큐를 구현하는 데 매우 효율적인 방법 중 하나이다.
- 힙을 사용하면 (우선순위에 따른) 삽입과 삭제 작업을 O(log n) 시간 안에 수행할 수 있다.
- 힙을 사용한 우선순위 큐 구현은 우선순위 변경이 자주 일어나는 대규모 데이터셋에 특히 유용하다.
3 같이 보기[ | ]
4 참고[ | ]
편집자 Jmnote Jmnote bot
로그인하시면 댓글을 쓸 수 있습니다.