자바(Java)예제로 구현한 힙(Heap) 자료 구조
힙(Heap) 이란 무었인가?
힙(Heap)은 완전 이진 트리(Complete Binary Tree)로, 각각의 노드가 자신의 부모 노드보다 작거나 같은 값을 저장하는 자료형 이다. 힙(Heap)은 완전 이진 트리(Complete Binary Tree)라 가장 아래에 있는 노드들을 제외한 모든 노드들이 두 자식 노드를 모두 가지고 있거나 아예 자식 노드를 가지지 않는 특성을 가진다.- 만약 부모 노드가 자식 노드보다 크거나 같다면 그건 "Max Heap"(최대 힙)
- 부모 노드가 자식 노드보다 작거나 같다면 "Min Heap"(최소 힙) 이라 불린다.
힙(Heap) 컨셉힙(Heap)은 실제로 어디에 사용될까?
- Heapsort(힙 정렬)
- 우선 순위 큐(Priority Queue)
- 힙 자료 구조는 우선 순위 큐를 구현하는데 많이 쓰인다
- 다양한 알고리즘(Algorithm) 구현