알고리즘 2 - Priority Queue (우선순위 큐)
Priority Queue: insert()와 delete() 두 작업 수행하는 자료구조
Stack, Queue와 유사하게 다음 두 작업 수행
insert(e): 자료구조에 원소 e 추가
delete(): 자료구조에 저장된 원소 중 하나 반환하며 삭제(우선순위가 가장 높은 원소를 반환)
****delMin() 하며 동시에 insert() 계속 되는 경우->PQ가 정렬보다 유리함****
Priority Queue 는 두가지에 따라 insert 비용과 delMin 비용이 달라진다
정렬상태 유지 안할때
맨 뒤에 (혹은 맨 앞에) 새 원소 추가하므로 insert() 비용 작음 Min은 탐색해야 하므로 delMin() 비용 큼
정렬상태 유지
정렬된 위치에 새 원소 추가하므로 insert() 비용 큼 Min은 항상 맨 앞에 있으므로 delMin() 비용 작음
Complete Binary Tree
Binary tree: 모든 노드의 자식이 최대 2개 (왼쪽, 오른쪽)
Complete tree:
(가장 아래 level 제외한) 모든 level이 빈 곳 없이 가득 차 있으며
가장 아래 레벨은 왼쪽부터 빈 곳 없이 차례로 채워진 트리
왜 tree 구조를 사용하는가? 접근 속도를 ~logN으로 하기 위하여 (depth 깊이 제한을 위해 complete tree 장점: 코드간단, 깊이제한)
~logN 시간에 수행되는 많은 방법이 트리에 기반함 (예: Quick Union for Union Find)
트리 깊이(높이)가 logN에 비례하도록 하고 필요한 작업 수행에 (예: insert(), delete()) 트리 깊이에 비례한시간 걸리도록 하면
~logN 시간에 수행하도록 할 수 있음
1. complete binary tree (complete 형태)
장점 1: 깊이 제한되는 균형 잡힌 트리
왼쪽부터 차곡차곡 빠짐없이 담는 구조이므로
트리가 한쪽으로만 길어지거나 하지 않아
깊이를 logN에 비례하게 유지 가능 (N은 정점 개수)
따라서 깊이에 비례한 횟수의 작업 하도록 할 때 (insert, delete 등) 비용을 logN으로 제한 가능
[Q] 정점 N개로 만든 이진 트리가 complete 이진 트리보다 더 얕아질 수 있는가?
장점 2: Linked list 아닌 배열에 담을 수 있어 편리
왼쪽부터 차곡차곡 빠짐없이 담는 구조의 트리이므로
(트리에 담는 순서 그대로) 배열에 왼쪽부터 차곡차곡 빠짐없이 담을 수 있음
배열에 담으면 부모-자식 간 링크 만들지 않아도 index 만으로 찾아갈 수 있어 메모리 절약 & 편리
Binary heap 구조에서
Priority queue에 필요한 insert(), delMax() 효율적 수행 위해 (maxPQ 가정)
Heap-order 조건 항상 만족하며 원소가 저장되도록 함
2. MAX heap order (insert 방법)
(Max) heap-order 조건: 부모 key ≥ 자식 key(Key: 여러 값으로 구성된 tuple 저장되어 있을 때, tuple 간 대소 비교에 사용하는 값)
insert():
1 complete binary tree 형태 유지하며 (부모 node 1 자식 node 2 형태)
2 heap order 유지하며 (부모key >= 자식key)
3~logN 시간에 새 원소 추가
priority Queue p.25
delMax(): complete binary tree 형태 유지하며 heap order 유지하며 ~logN 시간에 삭제
root 값을 tree 가장 마지막 값 k와 swap하며 배열에서 삭제
k를 자식 노드 중 큰 쪽과 비교해 heap-order (부모≥자식) 어긴다면 swap하는 것 반복 (sink)
(즉, heap-order 만족할 때까지 자식 노드 중 큰 쪽 따라 계속 내려감)
delMin():
풀어보기
**Binay heap(complete binary tree)구조에서
Priority queue에 필요한 insert(), delMax() 효율적 수행 위해 (maxPQ 가정) Heap-order 조건 항상 만족하며 원소가 저장되도록 함
priority queue 기본 -> complete binary tree(이진트리 들어온 순서대로) 와 max heap order(부모key>=자식Key, 부모노드와비교해 swap함(swim up)) 사용 하여 시간복잡도를 낮춤 ~NlogN
insert , delMAX, delMIN
complete binary tree:사용이유
배열에 담으면 부모자식간 링크리스트 만들지 않아도 index만으로 배열에서 찾아갈수있음으로 메모리 절약 편리함
참고 index 0은 배열 비워두고 index 1부터 삽입 //만약 0부터 삽입하면 node i를 찾을때 부모i=(i-1),자식 +1씩 되어서 더복잡함
node i의
부모: i//2
왼쪽 자식: i×2
오른쪽 자식: i×2 + 1
Priority queue에 필요한 효율적 수행때문에 밑에 조건을 붙인다:
insert : 1. complete binary tree 형태 유지하며 2. heap order 유지하며 3. ~logN 시간에 max 삭제
delMax(): 1. complete binary tree 형태 유지하며 2. heap order 유지하며 3. ~logN 시간에 max 삭제
따라서 배열 맨끝에 insert 한 후에 delMax or delMin 젤위 노드 삭제 후 배열 젤끝에 애들 넣음 밑으로 내려가면서 대소 비교
따라서 배열에서 정렬을 사용한다면 PQ 사용해도 큰문제는 없다
배열정렬(오름차순 (혹은 내림차순)으로 원소 하나씩 꺼내 사용하기 위해)하는데 NlogN PQ 사용해도 logN작업을 N회 수행 따라서 NlogN동일
정렬된 배열에 insert 할때는 N^2이라서 차라리 PQ가 안전함 NlogN
정렬사용시 비용은 insert 1회비용 ~1 횟수N :~N
예시 slider puzzle3*3배열 ->시작점 목표지점까지 최단경로 찾기
A* search 구현 방법: 예측 이동 횟수 가장 작은 경우부터 우선 탐색하기 위해 Algorithm 2, Priority Queue
Min Priority Queue 사용
예측이동횟수 : depth+ (hamming vs manhattan) <= 실제 이동횟수
예상 문제
[Q] delMax()할 때 root 삭제한 후, 자식 중 더 큰 쪽을 swim up 시키는 것 반복하면 안되나? 왜 마지막 원소를 root에 두고 sink 시키나?
맨끝 node를 안올리면 대소비교가 깨져 순서가 엉망이됨 complete binary tree가 깨짐
1. (a*serach)minPQ에 남아있는 상태 :pop한 애 제외하고 밑에 갈수있는애들전부
2.다음에 pop되는 상태는 무엇인가 : 예측이동횟수가 젤 작은애 == 현재까지 이동횟수(depth)+mabhattan
조건 1,2를 항상 둘다 만족하기 힘듬
조건 1. 예측횟수가 실제 이도횟수에 가까울수록 불필요한 탐색을 줄일수있어 해를 빨리찾기가능(방법 두가지 hamming배열자리가맞는지개수 vs manhattan 배열이동횟수) ->최적에 가까운해 구할때 좋음
조건 2. 예측횟수<=실제이동횟수 조건을 만족해야 a*search 찾은 해가 최소이동횟수를 보장함 ->반드시 최적의 해를 구할때 좋음