Priority Queue

Priority Queue(PQ)

Prioritized objects by Key

Main: insert(elem) (implicit key), removeMin()

Auxiliary: min(), size(), empty()

can have the same key 

Total Ordering: Comparison rule should be defined for every pair of keys

     counter example: '≥' based on both x and y   --> Partial Ordering

Selection-Sort: PQ is implemented with an unsorted sequence

    1. inserting elements into the PQ without sorting (n)

    2. Removing from PQ to the sequence with sorting (n(n+1)/2)

Insertion-Sort: compare two and on

    1. inserting elements into the PQ with sorting (n(n+1)/2)

    2. Removing from PQ to the sequence without sorting (n)

Sorting by PQ: O(n²)

Comparator

How to design comparison logic?

1. Separate for different data type

    - hard to read code

2. Template and Overloading

    - cannot have multiple comparator 

3. Define comparator class & Overload "()" operator

Quiz: What is the advantage in 3rd design?

Composition method: each entry of PQ is pair(e, k)
Comparator method: compare two element

Heap

Sorting by heap: O(nlogn)   --> Where is unnecessary repetition?

Heap-order property: key(n) ≥ key(v.parent) (can be the same)

Complete binary tree:  every level except last level is completely filled

Insertion

   1. Find insertion node

   2. Upheap (swap to satisfy heap property)

Removal

   1. Replace root node with the last node

   2. Downheap (swap to satisfy heap property)

Find insertion node

   1. Go up until a left child or the root

   2. Go right child

   3. Go down until leaf

Vector-based heap implementation

- left child at 2i

- right child at 2i+1

Merging two heap: 

   1. create new heap with root really large key or given k

   2. downheap