🔗 참고 링크
https://www.youtube.com/watch?v=AjFlp951nz0
https://gyoogle.dev/blog/computer-science/data-structure/Heap.html
참고 링크의 강의 자료와 예시를 일부 가져와서 재 정리했습니다!
힙이란?
우선순위 큐를 위해 만들어진 자료구조이다.
우선순위 큐의 정의부터 알아야한다.
우선순위 큐란?
우선순위의 개념을 큐에 도입한 자료구조이다.
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
- 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.
- 예를 들면 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우
| 자료구조 | 추출되는 데이터 |
|---|---|
| 스택 (Stack) | 가장 나중에 삽입된 데이터가 먼저 나간다 |
| 큐 (Queue) | 가장 먼저 삽입된 데이터가 먼저 나간다 |
| 우선순위 큐 (Priority Queue) | 가장 우선순위가 높은 데이터 먼저 나간다 |
우선순위 큐는 언제 사용할까?
- 시뮬레이션 시스템
- 작업 스케줄링
- 수치해석 계산
- 배열, 연결리스트를 힙으로 구현한다 (힙으로 구현이 가장 효율적이다.)
우선순위 큐 구현 방법
- 단순히 리스트를 이용하여 구현
- 힙(heap)을 이용하여 구현
데이터 개수가 n개일 때, 구현 방식에 따라 시간 복잡도를 비교
| 우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
|---|---|---|
| 리스트 | O(1) | O(N) |
| 힙(Heap) | O(logN) | O(logN) |
단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. (힙 정렬)
이 경우 시간 복잡도는 O(NlogN)입니다.
힙(Heap)
- 완전 이진 트리의 자료구조의 일종
- 여러 값 중, 최대값 최소값을 빠르게 찾아내도록 만들어진 자료구조
- 반정렬 상태
- 힙 트리는 중복된 값 허용 (이진 탐색 트리는 중복값을 허용하지 않는다.)
완전 이진 트리
루트(root) 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리(tree)를 의미한다.
힙 종류
- 힙에서는 항상 루트 노드(root node)를 제거한다.
- 최소 힙(min heap)
- 루트 노드가 가장 작은 값을 가진다. = 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
- 값이 작은 데이터가 우선적으로 제거된다.
- 최대 힙(max heap)
- 루트 노드가 가장 큰 값을 가진다. = 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
- 값이 큰 데이터가 우선적으로 제거된다.
최소 힙 구성 함수 Min-Heapify()
Heapify()
일반적으로 힙을 구성하기 위한 함수의 이름
- 상향식
- 부모 노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체한다.
힙에 새로운 원소가 삽입될 때
Heapify를 활용하게 되면 새로운 원소가 삽입되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.
기본적으로 힙 자료구조는 완전 이진 트리를 따르기 때문에 균형잡힌 트리로써 동작한다.
항상 부모쪽으로 거슬러 올라가거나, 부모에서 자식으로 내려올때 최악의 경우에도 logN의 시간 복잡도를 보장한다.
Heapify를 호출했을 때 오른쪽 같이 전체트리가 갱신된다.
힙에서 원소가 제거될 때
원소가 제거되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다.
원소를 제거할 때는 가장 마지막 노드가 루트 노드에 위치에 오도록 한다.
이후에 루트 노드에서부터 하향식으로 (더 작은 자식 노드로) Heapify()를 진행한다.
