Priority_Queue ADT

key, value 두 가지 entry로 구성

key값이 작을수록 우선순위가 높다 -> min_priority_queue
key값이 클 수록 우선순위가 높다 -> max_priority_queue

PQ sorting

1. unsorted list - selection sort
2. sorted list - insertion sort 
3. heap sort

---

Unsorted List - Selection Sort 

원소를 주어지는 순서대로 삽입 -> O(1)

삽입된 원소를 하나하나 비교해가며 찾아서 반환 -> O(n)

 

그러므로

n개의 원소 삽입 -> O(n)

최솟값 / 최댓값을 찾아 반환 -> O(n^2)

=> worst-case 가 곧 average-case

 

Sorted List - Insertion Sort

-> 사이즈가 작을 때 유용.

 

원소를 처음부터 정렬시켜가며 삽입 -> O(n)

삽입된 원소를 순서대로 반환 -> O(1)

 

그러므로

n개의 원소 삽입 -> O(n^2)

최솟값 / 최댓값을 찾아 반환 -> O(n)

 

 

비교

 

worst case는 sorted, unsorted 모두 똑같으나
average case는 sorted list가 더 빠르다.

selection sort : average = n^2/2;

insertion sort : average = n^2/4;

 

예시

 

컴퓨터 로그 파일 관리 : unsorted list 활용
검색을 많이 하는 경우 : sorted list를 활용

 

In-place-sort

in-place-sort : 필요한 추가 메모리가 상수인 경우
log(n)정도 사욯하는 경우에도 in-place-sort로 인정

selection sort, insertion sort도 in-place-sort가 가능하다.

---

Heap

=> heap의 조건으로는 구조와 순서를 만족해야한다.

구조 : 항상 Complete Binary Tree의 형태이다.

순서 : 루트 노드를 제외한 모든 원소에 대해 key(v) >= key(parent(v)) 를 만족

but) 자신의 직계 부모보다 작아야하지만 직계가 아닌 부모의 반계 관계와는 대소가 관계가 없다. (partial order)

last node : 가장 마지막에 삽입된 원소 (위치가 중요함)

->Complete Binary Tree에서 높이 노드에 있는 노드 중 맨 오른쪽에 위치한 노드

 

Height

 

Complete Binary Tree를 만족하기때문에 Tree의 높이는 log2(n)보다 클 수 없다.

 

Insert (UpHeap)

 

Insertion -> 구조를 먼저 완성시킴

1. last node의 다음 위치에 데이터 삽입
2. 자신의 parent로 올라가며 대소 비교
3. 만약 자신의 value가 parent의 value보다 작다면 순서 변경
4. 3의 과정을 parent가 root || 클 때까지 반복

-> O(log(n))

 

Remove (DownHeap)

 

1. last node의 key-value를 root에 삽입
2. last node를 이전 노드로 변경
3. root부터 자신의 child와 비교
4. 자신보다 작은 값이 있는지 비교 + 둘 중 더 작은 값을 비교 -> 비교연산 2 번 진행
5. 3 ~ 4의 과정을 child가 NULL || 클 때까지 반복

->O(log(n))

 

Update Last Node

 

1. 자신이 parent의 left-child || root일 때까지 위로 올라감.
2. root라면 right로 이동, 아니라면 parent의 right로 이동
3. child가 NULL이 아닐 때까지 left로 이동

-> traverse O(log(n))

---

Heap-Sort

• 사용하는 공간O(n)
• insert, remove 시간 복잡도 O(log(n))

-> n개의 원소에 대해 진행하므로 O(nlog(n))이 된다.

=> selection sort, insertion sort보다 매우 빠르다.

 

Vector-based Heap

 

힙은 배열로 구현
-> last node = heap size
-> 더 빠름

-> 구조 조건을 이미 만족

 

Tree와 마찬가지로 0번째 index는 비워둠.

i 부모 노드의 자식 노드 index는 2 * i, 2 * i + 1이 된다.

in-place-sort도 가능 (0번째 index를 활용)

1단계
number of road edges <= total number of edges (n - 1)
한 번 내려갈 때 비교 연산 횟수 = 2
전체 비교 연산 횟수 = 2*number of road edges
전체 비교 연산 횟수 <= 2(n - 1) = O(n)
=> O(N) 걸림

2단계는 O(nlog(n))보다 빠를 수 없음
가장 작은 min인 A[1]을 A[0]으로 복사
A[n]을 A[1]로 옮기면
힙 사이즈 = n - 1
다시 힙으로 구현 (remove 처럼)
A[0]를 A[n]으로 복사
.
.
.
마지막에는 내림차순 정렬 되어있음
=> inplace sort가 가능

1단계 : O(n)
2단계 : O(nlogn)

 

Merging two Heaps

 

-> bottom-up 방식으로 아래서부터 heap을 합침

-> downheap으로 정렬

 

2^i - 1, 2^i - 1 두 개의 heap을 합치면

2^(i+1) - 1개의 원소가 된다.

시간복잡도는 O(n)이다.