[Algorithm] 자료구조1 : Graph, Binary Tree, Heap, Priority Queues
Graph
- 표현법
- (b) : linked list
-
memory size : V + E
-
- (c) : matrix
-
memory size : V ^2 -
구현 쉽지만 v 커지면, 너무 Memory와 수행 시간 커짐
-
- (b) : linked list
Binary Tree
- 자식이 0~2개인 Tree
용어
- degree : 자식 노드 수
- external node : leaf 노드, degree = 0
- interneal node : leaf가 아닌 노드, degree > 0
- depth : root까지 최단 거리 (=level)
-
height : leaf까지 최단 거리
종류
- Full Binary Tree
- 자식은 없거나 2개
- Perfact Binary Tree
- 자식은 없거나 2개 + 모든 level의 깊이 같다.
- Complete Binary Tree
- 왼쪽 위부터 차례로 채운 형태
- height h = floor($log_2n$)
Heap
-
왼쪽 위부터 차례로 저장하는, Complete binary Tree
- 구성 요소
- heapsize : 포함한 element 수
- parent : return floor(i/2)
- left child : return (2*i)
- right child : return (2*i + 1)
-
코드
- 종류
- Max-heap : 위로 갈수록 크다.
- Min-heap : 아래로 갈수록 크다.
- 기능
- MAX_Heapify : Max heap 되게 만들기
-
leaf까지 타고 내려가며, 자식 중 더 작은 것과 swap
-
complexity : O(h)
- 증명있다고 하시는데… 그냥 아래로 타고 내려가니 높이 만큼 실행하니 당연한 듯.
-
- Build Max Heap
- bottom-up으로 max_heapify 호출
- 뒤에서부터 볼 때, leaf 아닌 첫 노드(floor(n/2))에서 시작
- leaf는 이미 maxheap 상태라고 볼 수 있다.
- O(n) 정도 시간 걸림
- 중간에서 호출하는 max-heapify들은 높이가 전체 tree의 height 아님.
- MAX_Heapify : Max heap 되게 만들기
- Heapsort
- 1) max heap 만들기
- 2) 아래 반복
- root를 출력
- 맨 뒤 노드부터 하나 씩 root랑 바꾼 후, root에서 max-heapify
Priority Queues
- 들어온 순서 대신, 부여한 우선순위대로 나가는 Queue
- heap과 key(priority) 사용
- 여러 operation들이 다 O(lg n)
- 기능
-
maximum(S) : largest key 갖는 element 찾기
- extract_max(S) : largest key 갖는 element를 dequeue
- 맨 마지막 노드를 root로 올린 후, Max-heapify
- increase_key(S, x, k) : element x의 key를 k로 바꾸기
- 부모랑 비교해서 swap하며, root까지 타고 올라가기
- increase라서 k > x.key 이어야 함(반대로 decrease도 같이 만들수도 있음)
- insert(S, x, k) : key k를 갖는 x를 enqueue
- 마지막 위치에, - $\infin$ key로 넣은 후, increase_key
-