Priority Queue

PriorityQueue

	1. Priority Queue: remove the largest/smallest item
2. Implementations
	1. Sort: NlgN time, N space
	2. elementary PQ: MN time, M space
	3. Binary heap: NlogM time, M space (best in practice)
	4. unordered array: insert 1, del max N, max N
	5. ordered array: insert N, del max 1, max 1
3. Binary Heap
	1. Based on complete binary tree (perfectly balanced except for bottom level)
	2. Heap order
		1. Keys in nodes
		2. parent’s key no smaller than children’s keys
	3. Array representation
		1. indices start at 1, take nodes in level order, no explicit links needed
		2. 平铺 by levels
		3. parent of k is at k/2, children of k is at 2k and 2k+1
	4. Promotion
		1. exchange key in child with key in parent, repeat until heap order restored
		2. Insert is to add at the end and promote
	5. Demotion
		1. exchange key in parent with key in larger child, repeat until heap order restored
		2. delete is to exchange root with node at the end and then demotion
	6. insert logN, delmax logN
	7. d-way heap (works slightly better)
	8. Fibonacci heap (insert in constant time and delete in logN time)
	9. Best practices
		1. Use immutable keys (final)
			1. priority queue
			2. symbol table
		2. underflow and overflow
		3. remove an arbitrary item and change the priority can be implemented usign swim and sink
4. Heapsort
	1. Create max-heap with all N keys
	2. repeated remove the maximum key
	3. Heap construction uses <=2N compares and exchanges
	4. Heapsort uses <=2NlogN compares and exchanges
	5. First in-place sorting algorithm with NlogN worst-case
	6. Optimal for both time and space
	7. Bottom line
		1. inner loop longer than quicksort's
		2. make poor use of cache memory (do not have local memory search)
		3. not stable
5. Event-driven simulation
	1. Time-driven simulation
		1. update the position of each particle after every dt units of time and check for overlaps
		2. ~N^2/2 overlap checks per time quantum
		3. simulation is too slow if dt is very small
		4. Many miss collisions if dt is too large
	2. Event-driven simulation
		1. Focus only on times with collision occur
		2. Maintain PQ of collision events, prioritized by time
		3. Remove the min