●Priority Queues
▷우선순위의 개념으로 entry들의 집합을 저장함.
▷entry: key, value의 짝
▷위치가 아닌 우선순위를 기준으로 저장
▶메소드
▶Main Methods
▷Insert(e) : entry e 추가.
▷removeMin() : key값이 가장 작은 값(들)을 제거, return
▶Additional Methods
▷min() : 가장 작은 key를 return (지우진 않음)
▷size()
▷empty()
▶Total Order Relation
▷Key값 : 순서가 명시되는 arbitary object여야함.
▷다른 2개의 entry가 동일한 key를 가질 수 있다.
▶비교 규칙
▷Reflexive property (반사성) : x ≤ x
▷Antisymmetric property (비대칭성) : x ≤ y ∧ y ≤ x => x = y
▷Transitive property (이행성) : x ≤ y ∧ y ≤ z => x ≤ z
○Sequence-based Priority Queue
▶Unsorted List
▷정렬되지 않는 상태로 저장
▶Algorithm
▷Insert : O(1) - 바로 넣음.
▷removeMin : O(n) - 가장 작은 값 찾아야 함.
▶Sorted List
▷정렬된 상태로 저장
▶Algorithm
▷Insert : O(n) - 적절한 위치에 넣어야 함.
▷removeMin : O(1) - 가장 앞의 값
○Priority Queue Sorting
▷1. 모든 element들을 priority queue에 넣음.
▷2. removeMin으로 가장 작은 element부터 가져옴.
▶Selection Sort
▷Unsorted List를 이용
▷1. n개의 insert -> O(n)
▷2. n번의 removeMin -> 1+2+...n = n(n-1)/2
▷-> O(n2)
▶Insertion Sort
▷Sorted List를 이용
▷1. n개의 insert -> 1+2+...n = n(n-1)/2
▷2. n번의 removeMin -> O(n)
▷-> O(n2)
○Comparator
▷우선순위 비교를 위한
▶isLess(p, q)
▷return p < q;
▷같다 : !isLess(p, q) && !isLess(q, p)