[자료구조] Heap

✅ 힙 (Heap)

❕ 기본 개념 

- 그래프의 이진 트리 구조 중 하나

- 힙을 표현하는 트리 구조의 각 정점을 노드(node)라고 부르며, 각 노드에는 데이터가 저장됨

- 중복된 값을 허용함

- 두 가지의 힙 타입이 존재: Max-Heap / Min-Heap

 

Min-Heap의 경우...

- 항상 최상위 노드에 최솟값이 존재하므로, 데이터 수와 상관없이 항상 O(1) 시간에 최솟값을 추출할 수 있음

- 최솟값 추출한 후에는 힙을 재구축하게 되는데, 이때 가장 후미에 있는 데이터를 가장 위로 끌어올린 후에 그 자식과 비교해가며 아래 방향으로 재구축을 진행함

- 데이터 수를 n이라 할 때, 트리의 높이는 log₂n이 되고 재구축하는데 걸리는 시간은 O(log n)이 됨

- 데이터를 추가할 때는 가장 후미에 데이터를 추가한 후, 힙 조건을 만족할 때까지 부모 숫자와 비교하며 위쪽으로 재구축을 진행함. 따라서 트리의 높이에 비례한 O(log n) 시간이 걸림 (즉, 데이터 삽입 & 삭제 모두 O(log n))

 

- 힙은 우선순위 큐(priority queue)를 구현할 때 사용됨

- 우선순위 큐는 데이터를 자유롭게 추가하고, 데이터를 추출할 때는 최솟값부터 순서대로 꺼냄

 

 

 

❕ 작동 방식 

 

☞ Max-Heap을 사용한 Heap sort

새로운 노드 삽입 후 재구축 과정, 최댓값 추출 후 재구축 과정을 볼 수 있다.

 

 

✔ 활용 예시 

관리하고 있는 데이터 중에서 최솟값/최댓값을 자주 추출해야 하는 경우에는 힙이 편리함.

 

- 네트워크 트래픽 제어

- 운영 체제에서의 작업 스케쥴링

- 다익스트라 알고리즘: 후보가 되는 노드 중에서 최솟값을 매 단계에서 선택해야함

 

 

 

참고자료

「알고리즘 도감」 中 1-7 힙

https://www.geeksforgeeks.org/heap-data-structure/

https://commons.wikimedia.org/wiki/File:Heap_sort_example.gif

https://velog.io/@yanghl98/자료구조-Heap힙-개념-종류-활용-예시-구현