- 본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.
* 해당 필기는 '춤추는 개발자'님의 https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9 블로그 포스팅을 참조했음을 밝힙니다.
힙은 트리 기반의 자료구조이다. 규칙에 따라 크게 두 가지 힙을 나눌 수 있는데
- Max Heap
- Min Heap
으로 나눌 수 있다.
힙 전체를 통틀어서 이 규칙이 꼭 유지되어야 한다. (이 글에서는 우선순위 큐와 연관을 짓기 위해서 Min Heap을 구현한다.)
일반적으로 힙 자료구조는 이진트리로 구현한다. 이진트리는 각각의 부모노드는 오로지 두개의 자식 노드(left, right) 만 가질 수 있는 트리를 의미한다. 추가적으로 힙은 완전한 이진트리의 구조를 사용하는데, 트리의 가장 아래 층을 제외하고는 상단의 모든 레벨이 완전히 채워져야 한다는 규칙이다.
- 부모 노드는 항상 자식 노드보다 값이 작아야 한다.
- 한 레벨이 모두 채워져야 다음 레벨로 트리가 늘어날 수 있다.
이 두 가지 규칙을 지키는 자료구조를 힙(Min Heap) 이라고 할 수 있다.
이 두 가지 규칙을 항상 따르는 힙은 이진트리 자료구조 임에도 불구하고 배열로 구현 할 수 있다.
- 왼쪽 자식 노드 index = 부모 노드 index*2 + 1
- 오른쪽 자식 노드 index = 부모 노드 index*2 + 2
- 부모 노드 index = (자식 노드 index - 1) / 2
위와 같은 트리를 아래 처럼 배열로 나타낼 수 있다.
- index: 0 1 2 3 4 5
- value: 1 4 8 5 2 3
힙은 왜 필요할까?
힙은 주로 최소 | 최대 값을 O(1)의 시간복잡도로 얻어내기 위해서 사용된다.
배열이나 연결 리스트 같은 자료구조는 선형 탐색으로 인해서 최소 | 최대 값을 얻기 위해서 O(n) 이 걸린다. 이진탐색을 이용하면 O(logn) 까지도 시간 복잡도를 줄일 수 있다.
Min Heap 은 위의 두 가지 규칙 덕분에 항상 최상위 부모 노드에 최소값이 담겨있게 된다. 따라서 최상위 노드만 조회하면 바로 최소 값을 얻어낼 수 있기 때문에 O(1) 의 시간 복잡도를 가진다고 할 수 있다.
실제로는 어디에 쓰일까? 힙과 우선순위 큐를 같은 자료구조라고 볼 수 는 없지만, Min Heap 의 특성상(부모 노드는 항상 자식 노드보다 값이 작아야 한다) 우선순위 큐를 구현하는데 최적의 자료구조가 된다. 따라서 우선순위 큐의 사용처가 곧 힙의 사용처가 될 수 있다.
- 우선순위 큐를 구현하는데 사용 할 수 있다.
- 운영체제에서 우선순위 기반의 일들을 스케쥴링 하기 위해서 힙을 사용한다. (우선 순위가 높은 일을 바로 조회 할 수 있기 때문에)
- 다익스트라 알고리즘 - 내가 막혀서 힙부터 찾아보는 이유..(최단 거리 구하기 알고리즘) 에서 최소 비용을 기반으로 그래프를 탐색 할 때 사용된다.
* 구현은 vs code에서
