자료구조 및 알고리즘 자료 Priority Queue

목차

1. Definition
2. Priority Queue Class
3. Applications
4. Operations

본문내용

Definition
-Definition
heap property 를 유지하는 data structure
max-heap → max-priority queue
min-heap → min-priority queue
-Data Member
A : set of elements (array)
heap-size[A] : heap size
-Operations ( max-priority queue 기준)
HEAP-MAXIMUM(A)
HEAP-EXTRACT-MAX(A)
HEAP-INCREASE-KEY(A, i, key)
MAX-HEAP-INSERT(A, key)

Priority Queue Class
-Class
class MaxPriorityQueue
{
public:
int HEAP-MAXIMUM(int* A);
int HEAP-EXTRACT-MAX(int* A);
void HEAP-INCREASE-KEY(int* A, int i, int key);
void MAX-HEAP-INSERT(int* A, int key);
protected:
int* A;
int heap_size;
};

Applications
(Ex) 경매 프로그램
최고가 낙찰 : max-priority-queue
(Ex) 입찰 프로그램
최저가 입찰 : min-priority-queue
(Ex) Job scheduling of machine
Min-priority queue: finish time of all jobs

참고 자료

없음