📝오늘 공부한 것
- 프로그래머스 문제풀기
- 스파르타코딩클럽 자료구조 & 알고리즘 2주차 강의 듣기
알게 된 점❗
[ 최대 힙 ]
Heap(힙)
- 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
- 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조
- 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다.
- 그렇게 되면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 간다. 따라서 최대의 값들을 빠르게 구할 수 있다.
- 최댓값이 맨위인 힙을 Max Heap, 최솟값이 맨 위인 힙은 Min Heap이라고 한다.
- 이진트리와는 다르게 좌, 우 자식의 위치가 대소관계를 반영하지 않는다.
- 계산 편의를 위해 인덱스는 1부터 사용한다.
최대 힙 - 삽입 알고리즘
합의 규칙 : 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 한다.
따라서, 원소를 추가할 때는
1. 원소를 맨 마지막에 넣는다.
2. 부모 노드와 비교한 뒤 더 크다면 자리를 바꾼다.
3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2.과정을 반복한다.
최대 힙 - 삽입 시간복잡도
완전 이진트리의 최대 높이는 O(log(N))이고, 반복하는 최대 횟수도 O(log(N)) 이다.
즉, Max Heap의 원소 추가는 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있다.
최대 힙 - 추출 알고리즘
최대 힙에서 원소를 추출하는 방법은 최댓값, 루트 노드를 삭제하는 것이다.
스택과 같이 맨위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수 없다.
따라서, 원소를 삭제할 때는
1. 루트 노드와 맨끝에 있는 원소를 교체한다.
2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.
3. 변경된 노드와 자식 노드들을 비교한다. 두 자식 둥 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다.
4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복한다.
5. 2에서 제거한 원래 루트 노드를 반환한다.
최대 힙 - 추출 시간복잡도
완전 이진트리의 최대 높이는 O(log(N))이고, 반복하는 최대 횟수도 O(log(N)) 이다.
즉, Max Heap의 원소 삭제는 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있다.
'TIL(Today I Learned)' 카테고리의 다른 글
TIL-231004(자료구조 & 알고리즘 3주차) (0) | 2023.10.04 |
---|---|
TIL-231003(자료구조 & 알고리즘 2주차) (0) | 2023.10.03 |
TIL-230930(자료구조 & 알고리즘 1주차) (0) | 2023.09.30 |
TIL-230929(자료구조 & 알고리즘 1주차) (0) | 2023.09.29 |
TIL-230928(자료구조 & 알고리즘 1주차) (0) | 2023.09.28 |