[자료구조] Chapter 08. 우선순위 큐 (Priority Queue)

🚨 'C언어로 쉽게 풀어쓴 자료구조' 라는 책을 활용했던 과거 수업 필기를 정리한 것입니다.
💡 Chapter 순서는 책과 같지만 교수님의 과거 수업 내용에 따라 일부 책과 다른 내용이 있습니다.

※ n개의 데이터 sorting 하는데 걸리는 최소의 시간 nlg n

Heap 의 성질

• P >= L, R (Max Heap)
• P <= L, R ( Min Heap)
• 삭제할 때 root를 삭제

1. 삽입 (Insert)

1. 맨 끝에 추가 (Size 증가)
2. 추가된 원소를 Heap이 되도록 올려보냄 (재귀적)
   

2. 삭제 (Delete)

1. root (최대값)를 삭제 (service)
2. 맨 끝 원소를 root로 이동 (size 감소)
3. root를 Heap이 되도록 내려보냄 (재귀적)
   

3. 초기 Heap 구성 (Heap Building)

배열 H[1, ... N]에 N개의 Data

1. Top - Down (하향식 구성)
   
2. Bottom - Up (상향식 구성)
   

4. Why Bottom - Up faster than Top - Down?

5. Heap Sorting

heap을 구성한 후 root를 N번 (정확히는 N-1번) 삭제하여 나열함으로 sorting -> O(Nlg N)

A[1, ..., N]
1. Building-Heap // Bottom - Up -> O(N)
2. for(k = N down to 2) {
	swap(A[1], A[k]) // 삭제
    	HeapDown(1, k-1) // 재정비
   }