[자료구조] 힙(Heap) 1
in Study on Data Structure
힙이란?
데이터에서 최댓값과 최솟값을 빠르게 찾기 위헤서 고안된 완전이진트리이다.
최하단 왼쪽 노드부터 차례로 값이 삽입된다.
힙과 배열의 차이점
배열된 데이터를 가지는 자료구조라는 공통점은 있지만, 최댓값이나 최솟값을 찾으려면 시간복잡도가 $O(n)$인 배열에 반해, 힙의 시간복잡도는 $O(logn)$이 소요된다.
따라서, 최댓값과 최솟값을 빠르게 찾아야하는 상황에서 힙이 사용된다.
힙과 이진트리의 차이점
이진트리는 분기점의 값보다 큰 값이면 오른쪽으로, 작은 값이면 왼쪽으로 배치시키는 구조였지만, Max Heap은 부모노드의 값이 자식노드의 값보다 크고, Min Heap은 부모노드의 값이 자식노드의 값보다 작다는 점을 가지고 있다.
즉, 값을 비교해서 부모노드와 자식노드가 결정되는 것이다.
이진트리는 탐색에 중점, 힙은 최댓값 최솟값에 중점을 두었다고 보면 된다.
힙의 분류
- 최댓값을 찾기위한 Max Heap 구조
- 최솟값을 찾기위한 Min Heap 구조
크게 위의 두 가지로 나눌 수 있다.
