일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
- 벨만 포드
- python
- prim
- 유니온 파인드
- 크루스칼
- minimum spanning tree
- Longest Common Subsequence
- algorithm
- 우선 순위 큐
- 다이나믹 프로그래밍
- 최단 거리
- 넘파이
- 파이썬
- tree
- 최단 경로
- 강한 연결 요소
- 최소 신장 트리
- 트리
- Strongly Sonnected Coponent
- traceback
- 우선순위 큐
- 알고리즘
- 플로이드 위셜
- 최소 스패닝 트리
- priority queue
- 그래프
- numpy
- graph
- LCS
- 최장 공통 부분 수열
- Today
- Total
codinging
[자료구조] 우선순위 큐(Priority Queue) 와 힙(Heap) 알아보기 본문
우선순위 큐
우선순위 속성을 가지는 큐
우선순위 큐는 배열, 연결 리스트, 힙으로 구현 할 수 있다.
힙 구현 방식이 시간 복잡도가 가장 낮기 때문에 힙으로 구현한다.(O(logN))
힙
힙 순서 속성을 가지는 완전 이진 트리(자유 저장소 힙이 아님)
힙의 삽입 연산
🐬 1 : 힙의 최고 깊이 가장 우측에 새 노드 추가.(완전 이진 트리 유지)
🐬 2 : 삽입한 노드를 부모 노드와 비교한다. 삽입한 노드가 부모 노드보다 크면 맞는 위치니 연산 종료.
🐬 3 : 삽입한 노드가 부모 노드보다 작으면 부모 노드와 삽입한 노드의 위치를 교환. 교환 후 2번 - 3번 반복
예시
다음 힙에 값이 7인 노드를 삽입하는 예시다.
값이 7인 노드를 힙의 마지막에 추가하고 부모 노드와 비교한다.
7은 31보다 작으므로 이 두 노드를 교환한다.
한 단계 올라온 7과 7의 부모를 비교한다.
7은 9보다 작으므로 두 노드를 교환한다.
7과 부모인 뿌리노드 를 비교한다.
뿌리노드 2가 더 작으므로 교환을 수행하지 않는다.
이렇게 노드 삽입이 종료 된다.
힙의 최솟값(뿌리 노드) 삭제 연산
🐬 1 : 힙의 마지막 노드를 뿌리 노드로 이동한다. (힙의 순서 속성 파괴, 재조정 필요)
🐬 2 : 옮겨온 노드의 양쪽 자식노드와 비교하여 작은 쪽 자식노드와 위치를 교환한다.
🐬 3 : 옮겨온 노드가 자식노드가 없거나 자식 노드 보다 작은 값을 가지면 연산을 종료한다. (아닐 경우 2번 - 3번 반복)
예시
루트 노드를 삭제하고 마지막 노드의 값을 루트 노드에 대입한다.
옮겨진 노드와 그 자식 노드를 비교하여 작은쪽과 교환한다.
자식 노드가 더 작지 않을때 까지 반복 한다.
자식 노드가 더 크므로 종료한다.
힙 의 값을 저장
깊이 n의 노드는 배열 2ⁿ-1 ~ 2*2ⁿ-2 번 인덱스에 저장된다.
또, k번 인덱스의 자식노드는
왼쪽 : 2k + 1
오른쪽 : 2k + 2