Question? Leave a message!




PRIORITY QUEUES

PRIORITY QUEUES
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 2.4 PRIORITY QUEUES API and elementary implementations ‣ binary heaps ‣ heapsort ‣ Algorithms FOUR TH EDITION eventdriven simulation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu Last updated on 3/29/17 9:01 AM2.4 PRIORITY QUEUES API and elementary implementations ‣ binary heaps ‣ heapsort ‣ Algorithms eventdriven simulation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduCollections A collection is a data type that stores a group of items. data type core operations data structure PUSH, POP stack linked list, resizing array ENQUEUE, DEQUEUE queue linked list, resizing array INSERT, DELETEMAX priority queue binary heap PUT, GET, DELETE symbol table binary search tree, hash table ADD, CONTAINS, DELETE set binary search tree, hash table “ Show me your code and conceal your data structures, and I shall continue to be mystified. Show me your data structures, and I won't usually need your code; it'll be obvious.” — Fred Brooks 3Priority queue Collections. Insert and delete items. Which item to delete 
 Stack. Remove the item most recently added. Queue. Remove the item least recently added. Randomized queue. Remove a random item. 
 Priority queue. Remove the largest (or smallest) item. return contents contents Generalizes: stack, queue, randomized queue. operation argument size value (unordered) (ordered) insert P 1 P P insert Q 2 P Q P Q insert E 3 P Q E E P Q remove max Q 2 P E E P insert X 3 P E X E P X insert A 4 P E X A A E P X insert M 5 P E X A M A E M P X remove max X 4 P E M A A E M P insert P 5 P E M A P A E M P P insert L 6 P E M A P L A E L M P P insert E 7 P E M A P L E A E E L M P P remove max P 6 E M A P L E A E E L M P 4 A sequence of operations on a priority queuePriority queue API Requirement. Items are generic; they must also be Comparable. 
 Key must be Comparable 
 (bounded type parameter) 
 public class MaxPQKey extends ComparableKey 
 MaxPQ() create an empty priority queue 
 MaxPQ(Key a) 
 create a priority queue with given keys 
 insert(Key v) void insert a key into the priority queue 
 delMax() Key return and remove a largest key 
 isEmpty() boolean is the priority queue empty 
 
 max() Key return a largest key 
 size() int number of entries in the priority queue 
 
 Note. Duplicate keys allowed; delMax() picks any maximum key. 5Priority queue: applications Eventdriven simulation. customers in a line, colliding particles Numerical computation. reducing roundoff error Discrete optimization. bin packing, scheduling Artificial intelligence. A search Computer networks. web cache Operating systems. load balancing, interrupt handling Data compression. Huffman codes Graph searching. Dijkstra's algorithm, Prim's algorithm Number theory. sum of powers Spam filtering. Bayesian spam filter Statistics. online median in data stream 6Priority queue: client example Challenge. Find the largest m items in a stream of n items. Fraud detection: isolate transactions. n huge, m large NSA monitoring: flag most suspicious documents. 
 Constraint. Not enough memory to store n items. Transaction data
 type is Comparable (ordered by ) MinPQTransaction pq = new MinPQTransaction(); while (StdIn.hasNextLine()) use a minoriented pq String line = StdIn.readLine(); Transaction transaction = new Transaction(line); pq.insert(transaction); if (pq.size() m) pq now contains
 pq.delMin(); largest m items 7Priority queue: client example Challenge. Find the largest m items in a stream of n items. implementation time space sort n log n n elementary PQ m n m binary heap n log m m best in theory n m order of growth of finding the largest m in a stream of n items 8Priority queue: unordered and ordered array implementation r re et tur urn n c cont onte ents nts c cont onte ents nts o op pe er rat ation ion ar argume gument nt siz size e v value alue (unor (unorde der re ed) d) (or (orde der re ed) d) ins inse er rt t P 1 P 1 P P P P insert insert Q 2 P Q 2 P Q Q P P QQ ins inse er rt t E 3 P Q E E P Q E 3 P Q E E P Q r re emo mov ve max e max QQ 2 P E E P 2 P E E P insert insert X 3 P E X E P X X 3 P E X E P X ins inse er rt t A 4 P E X A A E P X A 4 P E X A A E P X insert insert M 5 P E X A M 5 P E X A M M A E A E MM P X P X remove max remove max X 4 P E M A A E M P X 4 P E M A A E M P insert insert P 5 P E M A P 5 P E M A P P A E M P A E M P PP insert insert L 6 P E M A P L A E L M P P L 6 P E M A P L A E L M P P ins inse er rt t E 7 P E M A P L E A E E L M P P E 7 P E M A P L E A E E L M P P remove max remove max PP 6 E M A P L E A E E L M P 6 E M A P L E A E E L M P A sequence of operations on a priority queue A sequence of operations on a priority queue 9Priority queue: implementations cost summary Challenge. Implement all operations efficiently. 
 
 
 
 implementation insert del max max 
 unordered array 1 n n 
 
 n 1 1 ordered array 
 goal log n log n log n 
 
 order of growth of running time for priority queue with n items 
 
 
 
 Solution. Partiallyordered array. 102.4 PRIORITY QUEUES API and elementary implementations ‣ binary heaps ‣ heapsort ‣ Algorithms eventdriven simulation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduComplete binary tree Binary tree. Empty or node with links to left and right binary trees. Complete tree. Perfectly balanced, except for bottom level. 
 
 
 
 
 
 
 
 complete binary tree with n = 16 nodes (height = 4) 
 
 Property. Height of complete binary tree with n nodes is ⎣lg n⎦. Pf. Height increases only when n is a power of 2. 12A complete binary tree in nature 13Binary heap: representation Binary heap. Array representation of a heapordered complete binary tree. 
 Heapordered binary tree. Keys in nodes. Parent's key no smaller than
 children's keys. i i 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 ai T S R P N O A E I H G ai T S R P N O A E I H G 
 TT Array representation. S R S R Indices start at 1. P N O A P N O A Take nodes in level order. No explicit links needed E I H G E I H G 11 TT 33 22 SS RR 66 77 55 44 PP NN OO AA 10 10 11 11 88 99 EE II HH GG Heap r Heap repr epresen esenta tations tions 14Binary heap: properties Proposition. Largest key is a1, which is root of binary tree. 
 Proposition. Can use array indices to move through tree. Parent of node at k is at k/2. Children of node at k are at 2k and 2k+1. i 0 1 2 3 4 5 6 7 8 9 10 11 ai T S R P N O A E I H G T S R P N O A E I H G 1 T 3 2 S R 6 7 5 4 P N O A 10 11 8 9 E I H G Heap representations 15Binary heap demo Insert. Add node at end, then swim it up. Remove the maximum. Exchange root with node at end, then sink it down. heap ordered T P R N H O A E I G T P R N H O A E I G 16Binary heap demo Insert. Add node at end, then swim it up. Remove the maximum. Exchange root with node at end, then sink it down. heap ordered S R O N G A P E I H S R O N P G A E I H 17Binary heap: promotion Scenario. A key becomes larger than its parent's key. 
 To eliminate the violation: Exchange key in child with key in parent. Repeat until heap order restored. S 
 P R private void swim(int k) 
 5 N T O A 
 violates heap order while (k 1 less(k/2, k)) E I H G (larger key than parent) 
 1 exch(k, k/2); 
 T k = k/2; 2 S R 
 parent of node at k is at k/2 5 N P O A 
 E I H G 
 Bottomup reheapify (swim) 
 
 Peter principle. Node promoted to level of incompetence. 18Binary heap: insertion Insert. Add node at end, then swim it up. Cost. At most 1 + lg n compares. insert remove the maximum key to remove T T P R S R N H O A N P O A exchange key key to insert E I G S E I G H with root public void insert(Key x) violates T H heap order pq++n = x; P R S R swim(n); N H O A N P O A remove node add key to heap E I G S E I G T from heap violates heap order T S swim up S R P R sink down N P O A N H O A E I G H E I G Heap operations 19Binary heap: demotion Scenario. A key becomes smaller than one (or both) of its children's. 
 why not smaller child To eliminate the violation: Exchange key in parent with key in larger child. Repeat until heap order restored. 
 violates heap order private void sink(int k) (smaller than a child) T 
 2 children of node at k H R while (2k = n) 
 are 2k and 2k+1 5 P S O A 
 E I N G int j = 2k; 
 if (j n less(j, j+1)) j++; T if (less(k, j)) break; 2 
 S R exch(k, j); 5 P N O A 
 k = j; 10 E I H G 
 Topdown reheapify (sink) 
 
 Power struggle. Better subordinate promoted. 20Binary heap: delete the maximum Delete max. Exchange root with node at end, then sink it down. Cost. At most 2 lg n compares. insert remove the maximum key to remove T T P R S R N H O A N P O A public Key delMax() exchange key key to insert E I G S E I G H with root Key max = pq1; violates T H heap order exch(1, n); P R S R sink(1); prevent loitering pqn+1 = null; N H O A N P O A return max; remove node add key to heap E I G S E I G T from heap violates heap order T S swim up S R P R sink down N P O A N H O A E I G H E I G Heap operations 21Binary heap: Java implementation public class MaxPQKey extends ComparableKey private Key pq; private int n; fixed capacity public MaxPQ(int capacity) (for simplicity) pq = (Key) new Comparablecapacity+1; public boolean isEmpty() PQ ops return n == 0; public void insert(Key key) // see previous code public Key delMax() // see previous code private void swim(int k) // see previous code heap helper functions private void sink(int k) // see previous code private boolean less(int i, int j) return pqi.compareTo(pqj) 0; array helper functions private void exch(int i, int j) Key t = pqi; pqi = pqj; pqj = t; 22Priority queue: implementations cost summary implementation insert del max max unordered array 1 n n ordered array n 1 1 binary heap log n log n 1 orderofgrowth of running time for priority queue with n items 23DELETERANDOM FROM A BINARY HEAP Goal. Delete a random key from a binary heap in logarithmic time. S R H N G A P E J I 24DELETERANDOM FROM A BINARY HEAP Goal. Delete a random key from a binary heap in logarithmic time. 
 S 
 2 
 R H 
 N G A P 
 10 
 E J I 
 
 
 Solution. Pick a random index r between 1 and n. Perform exch(r, n). Perform either sink(r) or swim(r). 25DELETERANDOM FROM A BINARY HEAP Goal. Delete a random key from a binary heap in logarithmic time. 
 S 
 
 R H 
 6 N G A P 
 10 
 E J I 
 
 
 Solution. Pick a random index r between 1 and n. Perform exch(r, n). Perform either sink(r) or swim(r). 26Binary heap: practical improvements Do "halfexchanges" in sink and swim. Reduces number of array accesses. Worth doing. Z T L B X 27Binary heap: practical improvements Floyd's "bounce" heuristic. only 1 compare per node Sink key at root all the way to bottom. some extra compares and exchanges Swim key back up. Overall, fewer compares; more exchanges. R. W. Floyd 1978 Turing award F X Y N O L K E D 28Binary heap: practical improvements Multiway heaps. Complete dway tree. Parent's key no smaller than its children's keys. Fact. Height of complete dway tree on n nodes is log n. d Z Y T G J X P W I K A B D E H F R S V C L M Q N O 3way heap 29Priority queues: quiz 1 How many compares (in the worst case) to insert in a dway heap A. log n 2 B. log n d C. d log n 2 D. d log n d E. I don't know. 30Priority queues: quiz 2 How many compares (in the worst case) to deletemax in a dway heap A. log n 2 B. log n d C. d log n 2 D. d log n d E. I don't know. 31Priority queue: implementation cost summary implementation insert del max max unordered array 1 n n ordered array n 1 1 binary heap log n log n 1 sweet spot: d = 4 dary heap log n d log n 1 d d † Fibonacci 1 log n 1 Brodal queue 1 log n 1 impossible 1 1 1 why impossible † amortized orderofgrowth of running time for priority queue with n items 32Binary heap: considerations Underflow and overflow. Underflow: throw exception if deleting from empty PQ. Overflow: add noarg constructor and use resizing array. 
 leads to log n amortized time per op Minimumoriented priority queue. (how to make worst case) Replace less() with greater(). Implement greater(). 
 Other operations. Remove an arbitrary item. can implement efficiently with sink() and swim()
 stay tuned for Prim/Dijkstra Change the priority of an item. 
 Immutability of keys. Assumption: client does not change keys while they're on the PQ. Best practice: use immutable keys. 33Immutability: implementing in Java Data type. Set of values and operations on those values. Immutable data type. Can't change the data type value once created. 
 public class Vector 
 instance variables private and final private final int n; 
 (neither necessary nor sufficient,
 private final double data; but good programming practice) 
 public Vector(double data) 
 this.n = data.length; 
 this.data = new doublen; defensive copy of mutable 
 for (int i = 0; i n; i++) instance variables this.datai = datai; 
 instance methods don't 
 ⋮ change instance variables 
 
 
 Immutable. String, Integer, Double, Color, Vector, Transaction, Point2D. Mutable. StringBuilder, Stack, Counter, Java array. 34Immutability: properties Data type. Set of values and operations on those values. Immutable data type. Can't change the data type value once created. Advantages. Simplifies debugging. Simplifies concurrent programming. More secure in presence of hostile code. Safe to use as key in priority queue or symbol table. Disadvantage. Must create new object for each data type value. “ Classes should be immutable unless there's a very good reason to make them mutable.… If a class cannot be made immutable, you should still limit its mutability as much as possible. ” — Joshua Bloch (Java architect) 352.4 PRIORITY QUEUES API and elementary implementations ‣ binary heaps ‣ heapsort ‣ Algorithms eventdriven simulation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduPriority queues: quiz 3 What is the name of this sorting algorithm 
 public void sort(String a) 
 
 int n = a.length; MaxPQString pq = new MaxPQString(); 
 for (int i = 0; i n; i++) pq.insert(ai); 
 for (int i = n1; i = 0; i) 
 ai = pq.delMax(); 
 A. Insertion sort. B. Mergesort. C. Quicksort. D. None of the above. E. I don't know. 37Priority queues: quiz 4 What are its properties 
 public void sort(String a) 
 
 int n = a.length; MaxPQString pq = new MaxPQString(); 
 for (int i = 0; i n; i++) pq.insert(ai); 
 for (int i = n1; i = 0; i) 
 ai = pq.delMax(); 
 A. n log n compares in the worst case. B. Inplace. C. Stable. D. All of the above. E. I don't know. 38sortdown heap construction 1 exch(1, 6) S X M sink(1, 5) 2 3 O R T S L E 4 5 6 7 E L E X A R A O P T P A 8 9 10 11 M P L E M O E E R S T X starting point (arbitrary order) starting point (heapordered) sink(5, 11) exch(1, 11) exch(1, 5) S T L sink(1, 10) sink(1, 4) O R P S E E L L M X A R A O P T O A P E E E E X S T X M M R sink(4, 11) exch(1, 10) exch(1, 4) S S E sink(1, 9) sink(1, 3) O R P R A E L L M X A E A O P T O L E X X M P E M E T R S T sink(3, 11) exch(1, 9) exch(1, 3) S R E Heapsort sink(1, 8) sink(1, 2) O X P E A E L L M A A P R E O T Basic plan for inplace sort. O L M P E E View input array as a complete binary tree. M S T X R S T X Heap construction: build a maxheap with all n keys. sink(2, 11) exch(1, 8) exch(1, 2) S P A Sortdown: repeatedly remove the maximum key. sink(1, 7) sink(1, 1) T O E X E E L L M R A E A O P P M L O E E S T X S T X M R R keys in arbitrary order build max heap sorted result sortdown sortdown heap construction heap construction (in place) (in place) 1 1 exch(1, 6) exch(1, 6) 1 exch(1, 7) S S X X M M O A sink(1, 5) sink(1, 5) sink(1, 6) sink(1, 11) 2 3 2 3 X 2 3 O O R R T T S S L L E E M E E E 4 4 5 56 7 6 7 T S 4 5 6 7 E L E E X A L R A E O P X A R A O P T T P P A A L M E P O P A L 8 9 10 11 8 9 10 11 L R A P E E 8 9 10 11 X P M L P E L O M E O E E S R T S X T M M R T X T X R S R S starting point (heapordered) starting point (arbitrary order) starting point (heapordered) starting point (arbitrary order) O E E M result (sorted) result (heapordered) sink(5, 11) exch(1, 11) exch(1, 5) sink(5, 11) 1 2 3 4 5 6 7 8 9 10 11 exch(1, 11) 1 2 3 4 5 6 7 8 9 10 11 exch(1, 5) 1 2 3 4 5 6 7 8 9 10 11 S T L S T L sink(1, 10) sink(1, 4) sink(1, 10) sink(1, 4) Heapsort: constructing (left) and sorting down (right) a heap S O R T E X A M P L E X T S P L R A M O E E A E E L M O P R S T X O R P S E E O R P S E E L L M A A P X R O T L O L A M X A R A O P T O A M P E E M E E X R S T X P E E E E X S T X M M R 39 sink(4, 11) exch(1, 10) exch(1, 4) sink(4, 11) exch(1, 10) exch(1, 4) S S E S S E sink(1, 9) sink(1, 3) sink(1, 9) sink(1, 3) O R P R A E O R P R A E L L M X A E A O P T O L L L M X A E A O P T O L E X X M P E M E T R S T M P E E M E T X R S T X sink(3, 11) exch(1, 9) exch(1, 3) sink(3, 11) exch(1, 9) exch(1, 3) S R E S R E sink(1, 8) sink(1, 2) sink(1, 8) sink(1, 2) O X P E A E O X P E A E L L M R A E A O P T O L L L M R A E A O P T O L P E E S T X S T X M M R P E E S T X S T X M M R sink(2, 11) exch(1, 8) exch(1, 2) sink(2, 11) S exch(1, 8) P exch(1, 2) A S P A sink(1, 7) sink(1, 1) sink(1, 7) sink(1, 1) T X O E E E T X O E E E L L M R A E A O P P M L L L M R A E A O P P M L O E E S T X S T X M R R M O E E R S T X R S T X 1 exch(1, 7) O 1 A exch(1, 7) O A sink(1, 6) sink(1, 11) sink(1, 6) X sink(1, 11) 2 3 X M E E E 2 3 M E E E T S 4 5 6 7 T S 4 5 6 7 L M E P O P A L L M P P E O A L L R A 8 9 10 11 P L R A 8 9 10 11 P R S T X R S T X S T X S T X R R E M O E result (sorted) M O E E result (sorted) result (heapordered) result (heapordered) Heapsort: constructing (left) and sorting down (right) a heap Heapsort: constructing (left) and sorting down (right) a heapHeapsort demo Heap construction. Build max heap using bottomup method. we assume array entries are indexed 1 to n array in arbitrary order 1 S 2 3 O R 4 5 6 7 A T E X 8 9 10 11 M P L E S O R T E X A M P L E 1 2 3 4 5 6 7 8 9 10 11 40Heapsort demo Sortdown. Repeatedly delete the largest remaining item. array in sorted order A E E L M O P R S T X A E E L M O P R S T X 1 2 3 4 5 6 7 8 9 10 11 41sortdown heap construction sor sort tdo down wn heap c heap construc onstruction tion 1 11 exch(1, 6) exch(1, 6) exch(1, 6) S X M SS XX MM sink(1, 5) sink(1, 5) sink(1, 5) 2 3 22 33 O R T S L E OO RR TT SS LL EE 4 5 6 7 44 55 66 77 E L E EE X A LL R A EE O P T XX AA P RR AA A OO PP TT PP AA 8 9 10 11 88 99 10 10 11 11 M P L E M O E E R S T X MM PP LL EE MM OO EE EE RR SS TT XX starting point (arbitrary order) starting point (heapordered) star start ting p ing point (ar oint (arb bit itr rar ary or y orde der) r) star start ting p ing point (heapor oint (heaporde der re ed) d) sink(5, 11) exch(1, 11) exch(1, 5) sink(5, 11) sink(5, 11) exch(1, 11) exch(1, 11) exch(1, 5) exch(1, 5) S T L SS TT LL sink(1, 10) sink(1, 4) sink(1, 10) sink(1, 10) sink(1, 4) sink(1, 4) O R P S E E OO RR PP SS EE EE Heapsort: heap construction L L M LL X A LL R A MM O P T XX AA O RR AA A OO PP TT OO AA M P E E M E E X R S T X MM PP EE EE MM EE EE XX RR SS TT XX First pass. Build heap using bottomup method. sink(4, 11) exch(1, 10) exch(1, 4) sink(4, 11) sink(4, 11) exch(1, 10) exch(1, 10) exch(1, 4) exch(1, 4) S S E SS SS EE sink(1, 9) sink(1, 3) sink(1, 9) sink(1, 9) sink(1, 3) sink(1, 3) O R P R A E OO RR PP RR AA EE for (int k = n/2; k = 1; k) L L M LL X A LL E A MM O P T XX AA O EE AA L OO PP TT OO LL sink(a, k, n); M P E E M E T X R S T X MM PP EE EE MM EE TT XX RR SS TT XX sor sort tdo down wn heap c heap construc onstruction tion sortdown heap construction sink(3, 11) exch(1, 9) exch(1, 3) sink(3, 11) sink(3, 11) exch(1, 9) exch(1, 9) exch(1, 3) exch(1, 3) S R E SS RR EE 11 sink(1, 8) sink(1, 2) 1 exch(1, 6) exch(1, 6) sink(1, 8) sink(1, 8) sink(1, 2) sink(1, 2) exch(1, 6) SS XX MM S X M sink(1, 5) sink(1, 5) sink(1, 5) O X P E A E OO XX PP EE AA EE 22 33 2 3 OO RR TT SS LL EE O R T S L E L L M LL R A LL E A MM O P T RR AA O EE AA L OO PP TT OO LL 44 55 66 77 4 5 6 7 EE LL EE E XX AA L RR AA E OO PP TT X A PP R A AA O P T P A M P E E M S T X R S T X MM PP EE EE MM SS TT XX RR SS TT XX 88 99 10 10 11 11 8 9 10 11 MM PP LL EE MM OO EE EE RR SS TT XX M P L E M O E E R S T X star start ting p ing point (ar oint (arb bit itr rar ary or y orde der) r) star start ting p ing point (heapor oint (heaporde der re ed) d) starting point (arbitrary order) starting point (heapordered) sink(2, 11) exch(1, 8) exch(1, 2) sink(2, 11) sink(2, 11) exch(1, 8) exch(1, 8) exch(1, 2) exch(1, 2) S P A SS PP AA sink(1, 7) sink(1, 1) sink(1, 7) sink(1, 7) sink(1, 1) sink(1, 1) sink(5, 11) sink(5, 11) exch(1, 11) exch(1, 11) exch(1, 5) exch(1, 5) sink(5, 11) exch(1, 11) exch(1, 5) SS TT LL S T T X O L E E E TT XX OO EE EE EE sink(1, 10) sink(1, 10) sink(1, 4) sink(1, 4) sink(1, 10) sink(1, 4) OO RR PP SS EE EE O R P S E E L A L A M P LL R AA LL E AA MM O PP P RR M EE L OO PP MM LL LL LL MM L XX AA L RR AA M OO PP TT X A OO R A AA O P T O A E E T X T X M O EE EE R S TT XX R S TT XX MM OO RR SS RR SS MM PP EE EE MM EE EE XX RR SS TT XX M P E E M E E X R S T X 1 exch(1, 7) 11 exch(1, 7) exch(1, 7) O A OO AA sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 11) sink(1, 11) sink(1, 11) X XX sink(4, 11) sink(4, 11) exch(1, 10) exch(1, 10) exch(1, 4) exch(1, 4) 2 3 sink(4, 11) exch(1, 10) exch(1, 4) 22 33 SS SS EE S S M E E E E MM EE EE EE sink(1, 9) sink(1, 9) sink(1, 3) sink(1, 3) sink(1, 9) sink(1, 3) T S TT SS 4 5 6 7 44 55 66 77 OO RR PP RR AA EE O R P R A E L M LL E P MM O P A EE PP L OO PP AA LL L LL R A 8 9 10 11 P RR AA 88 99 10 10 11 11 PP LL LL MM L XX AA L EE AA M OO PP TT X A OO E A LL O P T O L R S T X R S T X RR SS TT XX RR SS TT XX M O E E MM OO EE EE result (sorted) r res esult (s ult (sor ort te ed) d) MM PP EE EE MM EE TT XX RR SS TT XX M P E E M E T X R S T X result (heapordered) r res esult (heapor ult (heaporde der re ed) d) 42 Heapsort: constructing (left) and sorting down (right) a heap Heapsor Heapsort: c t: construc onstructing (lef ting (left) and sor t) and sorting do ting down (righ wn (right) a heap t) a heap sink(3, 11) sink(3, 11) exch(1, 9) exch(1, 9) exch(1, 3) exch(1, 3) sink(3, 11) exch(1, 9) exch(1, 3) SS RR EE S R E sink(1, 8) sink(1, 8) sink(1, 2) sink(1, 2) sink(1, 8) sink(1, 2) OO XX PP EE AA EE O X P E A E LL LL MM L RR AA L EE AA M OO PP TT R A OO E A LL O P T O L MM PP EE EE MM SS TT XX RR SS TT XX M P E E M S T X R S T X sink(2, 11) sink(2, 11) exch(1, 8) exch(1, 8) exch(1, 2) exch(1, 2) sink(2, 11) exch(1, 8) exch(1, 2) SS PP AA S P A sink(1, 7) sink(1, 7) sink(1, 1) sink(1, 1) sink(1, 7) sink(1, 1) TT XX OO EE EE EE T X O E E E LL AA LL AA MM PP L RR A L EE A M OO P PP R MM E LL O P M L EE EE TT XX TT XX MM OO E E RR SS T X RR SS T X M O R S R S 11 exch(1, 7) exch(1, 7) 1 exch(1, 7) OO AA O A sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 11) sink(1, 11) sink(1, 11) XX X 22 33 2 3 MM EE EE EE M E E E TT SS T S 44 55 66 77 4 5 6 7 LL MM L EE PP M OO PP AA E P LL O P A L LL L RR AA 88 99 10 10 11 11 PP R A 8 9 10 11 P RR SS TT XX RR SS TT XX R S T X R S T X MM OO EE EE M O E E r res esult (s ult (sor ort te ed) d) result (sorted) r res esult (heapor ult (heaporde der re ed) d) result (heapordered) Heapsor Heapsort: c t: construc onstructing (lef ting (left) and sor t) and sorting do ting down (righ wn (right) a heap t) a heap Heapsort: constructing (left) and sorting down (right) a heapHeapsort: sortdown sor sor sor sor sor sor sor sor sor sor sor sort t t t t t t t t t t tdo do do do do do do do do do do down wn wn wn wn wn wn wn wn wn wn wn heap c heap c heap c heap c heap c heap c heap c heap c heap c heap c heap c heap construc onstruc onstruc onstruc onstruc onstruc onstruc onstruc onstruc onstruc onstruc onstruction tion tion tion tion tion tion tion tion tion tion tion Second pass. 111111111111 exch(1, 6) exch(1, 6) exch(1, 6) exch(1, 6) exch(1, 6) exch(1, 6) exch(1, 6) exch(1, 6) exch(1, 6) exch(1, 6) exch(1, 6) exch(1, 6) SSSSSSSSSSSS XXXXXXXXXXXX MMMMMMMMMMMM sink(1, 5) sink(1, 5) sink(1, 5) sink(1, 5) sink(1, 5) sink(1, 5) sink(1, 5) sink(1, 5) sink(1, 5) sink(1, 5) sink(1, 5) sink(1, 5) 222222222222 333333333333 OOOOOOOOOOOO RRRRRRRRRRRR TTTTTTTTTTTT SSSSSSSSSSSS LLLLLLLLLLLL EEEEEEEEEEEE Remove the maximum, one at a time. 444444444444 555555555555 666666666666 777777777777 EEEEEEEEEEEE AAAAAAAAAAAA LLLLLLLLLLLL AAAAAAAAAAAA EEEEEEEEEEEE PPPPPPPPPPPP TTTTTTTTTTTT XXXXXXXXXXXX PPPPPPPPPPPP RRRRRRRRRRRR AAAAAAAAAAAA OOOOOOOOOOOO 888888888888 999999999999 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 MMMMMMMMMMMM PPPPPPPPPPPP LLLLLLLLLLLL EEEEEEEEEEEE MMMMMMMMMMMM OOOOOOOOOOOO EEEEEEEEEEEE EEEEEEEEEEEE RRRRRRRRRRRR SSSSSSSSSSSS TTTTTTTTTTTT XXXXXXXXXXXX Leave in array, instead of nulling out. star star star star star star star star star star star start t t t t t t t tt t ting p ing p ing p ing p ing p ing p ing p ing p ing p ing p ing p ing point (ar oint (ar oint (ar oint (ar oint (ar oint (ar oint (ar oint (ar oint (ar oint (ar oint (ar oint (arb b b b b b b b b b b bit it it it it it it it it it it itr r r r r r r r r r r rar ar ar ar ar ar ar ar ar ar ar ary or y or y or y or y or y or y or y or y or y or y or y orde de de de de de de de de de de der) r) r) r) r) r) r) r) r) r) r) r) star star star star star star star star star star star start t t t t t t t tt t ting p ing p ing p ing p ing p ing p ing p ing p ing p ing p ing p ing point (heapor oint (heapor oint (heapor oint (heapor oint (heapor oint (heapor oint (heapor oint (heapor oint (heapor oint (heapor oint (heapor oint (heaporde de de de de de de de de de de der r r r r r r r r r r re e e e e e e e e e e ed) d) d) d) d) d) d) d) d) d) d) d) sink(5, 11) sink(5, 11) sink(5, 11) sink(5, 11) sink(5, 11) sink(5, 11) sink(5, 11) sink(5, 11) sink(5, 11) sink(5, 11) sink(5, 11) sink(5, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 11) exch(1, 5) exch(1, 5) exch(1, 5) exch(1, 5) exch(1, 5) exch(1, 5) exch(1, 5) exch(1, 5) exch(1, 5) exch(1, 5) exch(1, 5) exch(1, 5) SSSSSSSSSSSS TTTTTTTTTTTT LLLLLLLLLLLL sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 10) sink(1, 4) sink(1, 4) sink(1, 4) sink(1, 4) sink(1, 4) sink(1, 4) sink(1, 4) sink(1, 4) sink(1, 4) sink(1, 4) sink(1, 4) sink(1, 4) OOOOOOOOOOOO RRRRRRRRRRRR PPPPPPPPPPPP SSSSSSSSSSSS EEEEEEEEEEEE EEEEEEEEEEEE LLLLLLLLLLLL XXXXXXXXXXXX AAAAAAAAAAAA LLLLLLLLLLLL RRRRRRRRRRRR AAAAAAAAAAAA MMMMMMMMMMMM OOOOOOOOOOOO PPPPPPPPPPPP TTTTTTTTTTTT OOOOOOOOOOOO AAAAAAAAAAAA while (n 1) MMMMMMMMMMMM PPPPPPPPPPPP EEEEEEEEEEEE EEEEEEEEEEEE MMMMMMMMMMMM EEEEEEEEEEEE EEEEEEEEEEEE XXXXXXXXXXXX RRRRRRRRRRRR SSSSSSSSSSSS TTTTTTTTTTTT XXXXXXXXXXXX sink(4, 11) sink(4, 11) sink(4, 11) sink(4, 11) sink(4, 11) sink(4, 11) sink(4, 11) sink(4, 11) sink(4, 11) sink(4, 11) sink(4, 11) sink(4, 11) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 10) exch(1, 4) exch(1, 4) exch(1, 4) exch(1, 4) exch(1, 4) exch(1, 4) exch(1, 4) exch(1, 4) exch(1, 4) exch(1, 4) exch(1, 4) exch(1, 4) SSSSSSSSSSSS SSSSSSSSSSSS EEEEEEEEEEEE exch(a, 1, n); sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 9) sink(1, 3) sink(1, 3) sink(1, 3) sink(1, 3) sink(1, 3) sink(1, 3) sink(1, 3) sink(1, 3) sink(1, 3) sink(1, 3) sink(1, 3) sink(1, 3) OOOOOOOOOOOO RRRRRRRRRRRR PPPPPPPPPPPP RRRRRRRRRRRR AAAAAAAAAAAA EEEEEEEEEEEE sink(a, 1, n); LLLLLLLLLLLL LLLLLLLLLLLL MMMMMMMMMMMM TTTTTTTTTTTT XXXXXXXXXXXX AAAAAAAAAAAA OOOOOOOOOOOO EEEEEEEEEEEE AAAAAAAAAAAA LLLLLLLLLLLL OOOOOOOOOOOO PPPPPPPPPPPP MMMMMMMMMMMM PPPPPPPPPPPP EEEEEEEEEEEE EEEEEEEEEEEE MMMMMMMMMMMM EEEEEEEEEEEE TTTTTTTTTTTT XXXXXXXXXXXX RRRRRRRRRRRR SSSSSSSSSSSS TTTTTTTTTTTT XXXXXXXXXXXX sink(3, 11) sink(3, 11) sink(3, 11) sink(3, 11) sink(3, 11) sink(3, 11) sink(3, 11) sink(3, 11) sink(3, 11) sink(3, 11) sink(3, 11) sink(3, 11) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 9) exch(1, 3) exch(1, 3) exch(1, 3) exch(1, 3) exch(1, 3) exch(1, 3) exch(1, 3) exch(1, 3) exch(1, 3) exch(1, 3) exch(1, 3) exch(1, 3) SSSSSSSSSSSS RRRRRRRRRRRR EEEEEEEEEEEE sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 8) sink(1, 2) sink(1, 2) sink(1, 2) sink(1, 2) sink(1, 2) sink(1, 2) sink(1, 2) sink(1, 2) sink(1, 2) sink(1, 2) sink(1, 2) sink(1, 2) OOOOOOOOOOOO XXXXXXXXXXXX PPPPPPPPPPPP EEEEEEEEEEEE AAAAAAAAAAAA EEEEEEEEEEEE LLLLLLLLLLLL LLLLLLLLLLLL MMMMMMMMMMMM RRRRRRRRRRRR AAAAAAAAAAAA EEEEEEEEEEEE AAAAAAAAAAAA OOOOOOOOOOOO PPPPPPPPPPPP TTTTTTTTTTTT OOOOOOOOOOOO LLLLLLLLLLLL EEEEEEEEEEEE XXXXXXXXXXXX XXXXXXXXXXXX MMMMMMMMMMMM PPPPPPPPPPPP EEEEEEEEEEEE MMMMMMMMMMMM SSSSSSSSSSSS TTTTTTTTTTTT RRRRRRRRRRRR SSSSSSSSSSSS TTTTTTTTTTTT sink(2, 11) sink(2, 11) sink(2, 11) sink(2, 11) sink(2, 11) sink(2, 11) sink(2, 11) sink(2, 11) sink(2, 11) sink(2, 11) sink(2, 11) sink(2, 11) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 8) exch(1, 2) exch(1, 2) exch(1, 2) exch(1, 2) exch(1, 2) exch(1, 2) exch(1, 2) exch(1, 2) exch(1, 2) exch(1, 2) exch(1, 2) exch(1, 2) SSSSSSSSSSSS PPPPPPPPPPPP AAAAAAAAAAAA sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 7) sink(1, 1) sink(1, 1) sink(1, 1) sink(1, 1) sink(1, 1) sink(1, 1) sink(1, 1) sink(1, 1) sink(1, 1) sink(1, 1) sink(1, 1) sink(1, 1) TTTTTTTTTTTT XXXXXXXXXXXX OOOOOOOOOOOO EEEEEEEEEEEE EEEEEEEEEEEE EEEEEEEEEEEE LLLLLLLLLLLL LLLLLLLLLLLL MMMMMMMMMMMM RRRRRRRRRRRR AAAAAAAAAAAA EEEEEEEEEEEE AAAAAAAAAAAA OOOOOOOOOOOO PPPPPPPPPPPP PPPPPPPPPPPP MMMMMMMMMMMM LLLLLLLLLLLL MMMMMMMMMMMM OOOOOOOOOOOO EEEEEEEEEEEE EEEEEEEEEEEE RRRRRRRRRRRR SSSSSSSSSSSS TTTTTTTTTTTT XXXXXXXXXXXX RRRRRRRRRRRR SSSSSSSSSSSS TTTTTTTTTTTT XXXXXXXXXXXX 111111111111 exch(1, 7) exch(1, 7) exch(1, 7) exch(1, 7) exch(1, 7) exch(1, 7) exch(1, 7) exch(1, 7) exch(1, 7) exch(1, 7) exch(1, 7) exch(1, 7) OOOOOOOOOOOO AAAAAAAAAAAA sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 6) sink(1, 11) sink(1, 11) sink(1, 11) sink(1, 11) sink(1, 11) sink(1, 11) sink(1, 11) sink(1, 11) sink(1, 11) sink(1, 11) sink(1, 11) sink(1, 11) XXXXXXXXXXXX 222222222222 333333333333 MMMMMMMMMMMM EEEEEEEEEEEE EEEEEEEEEEEE EEEEEEEEEEEE TTTTTTTTTTTT SSSSSSSSSSSS 444444444444 555555555555 666666666666 777777777777 LLLLLLLLLLLL EEEEEEEEEEEE PPPPPPPPPPPP MMMMMMMMMMMM OOOOOOOOOOOO PPPPPPPPPPPP AAAAAAAAAAAA LLLLLLLLLLLL LLLLLLLLLLLL PPPPPPPPPPPP RRRRRRRRRRRR AAAAAAAAAAAA 888888888888 999999999999 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 XXXXXXXXXXXX XXXXXXXXXXXX RRRRRRRRRRRR SSSSSSSSSSSS TTTTTTTTTTTT RRRRRRRRRRRR SSSSSSSSSSSS TTTTTTTTTTTT MMMMMMMMMMMM OOOOOOOOOOOO EEEEEEEEEEEE EEEEEEEEEEEE r r r r r r r r r r r res es es es es es es es es es es esult (s ult (s ult (s ult (s ult (s ult (s ult (s ult (s ult (s ult (s ult (s ult (sor or or or or or or or or or or ort t t t t t t t tt t te e e e e e e e e e e ed) d) d) d) d) d) d) d) d) d) d) d) r r r r r r r r r r r res es es es es es es es es es es esult (heapor ult (heapor ult (heapor ult (heapor ult (heapor ult (heapor ult (heapor ult (heapor ult (heapor ult (heapor ult (heapor ult (heaporde de de de de de de de de de de der r r r r r r r r r r re e e e e e e e e e e ed) d) d) d) d) d) d) d) d) d) d) d) 43 Heapsor Heapsor Heapsor Heapsor Heapsor Heapsor Heapsor Heapsor Heapsor Heapsor Heapsor Heapsort: c t: c t: c t: c t: c t: c t: c t: c t: c t: c t: c t: construc onstruc onstruc onstruc onstruc onstruc onstruc onstruc onstruc onstruc onstruc onstructing (lef ting (lef ting (lef ting (lef ting (lef ting (lef ting (lef ting (lef ting (lef ting (lef ting (lef ting (left) and sor t) and sor t) and sor t) and sor t) and sor t) and sor t) and sor t) and sor t) and sor t) and sor t) and sor t) and sorting do ting do ting do ting do ting do ting do ting do ting do ting do ting do ting do ting down (righ wn (righ wn (righ wn (righ wn (righ wn (righ wn (righ wn (righ wn (righ wn (righ wn (righ wn (right) a heap t) a heap t) a heap t) a heap t) a heap t) a heap t) a heap t) a heap t) a heap t) a heap t) a heap t) a heapHeapsort: Java implementation public class Heap public static void sort(Comparable a) int n = a.length; for (int k = n/2; k = 1; k) sink(a, k, n); while (n 1) exch(a, 1, n); sink(a, 1, n); but make static (and pass arguments) private static void sink(Comparable a, int k, int n) / as before / private static boolean less(Comparable a, int i, int j) / as before / private static void exch(Object a, int i, int j) / as before / but convert from 1based
 indexing to 0base indexing 44Heapsort: trace ai N k 0 1 2 3 4 5 6 7 8 9 10 11 init S O R T E X A M P L E ial values 11 5 S O R T L X A M P E E 11 4 S O R T L X A M P E E 11 3 S O X T L R A M P E E 11 2 S T X P L R A M O E E 11 1 X T S P L R A M O E E heapor X T S P L R A M O E E dered 10 1 T P S O L R A M E E X 9 1 S P R O L E A M E T X 8 1 R P E O L E A M S T X 7 1 P O E M L E A R S T X 6 1 O M E A L E P R S T X 5 1 M L E A E O P R S T X 4 1 L E E A M O P R S T X 3 1 E A E L M O P R S T X 2 1 E A E L M O P R S T X 1 1 A E E L M O P R S T X A E E L M O P R S T X sorted result Heapsort trace (array contents just after each sink) 45Heapsort: mathematical analysis Proposition. Heap construction makes ≤ n exchanges and ≤ 2 n compares. h+1 Pf sketch. assume n = 2 – 1 max number of exchanges to sink node 3 3 2 2 2 2 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 binary heap of height h = 3 a tricky sum (see COS 340) hh hh+1 +1 h+2(h 1)+4(h 2)+8(h 3)+...+2 (0) = 2 h 2 h+2(h 1)+4(h 2)+8(h 3)+...+2 (0) 2 = N (h 1) = N N 46Heapsort: mathematical analysis Proposition. Heap construction uses ≤ 2 n compares and ≤ n exchanges. Proposition. Heapsort uses ≤ 2 n lg n compares and exchanges. 
 algorithm can be improved to 1 n lg n (but no such variant is known to be practical) 
 
 Significance. Inplace sorting algorithm with n log n worstcase. inplace merge possible, not practical Mergesort: no, linear extra space. n log n worstcase quicksort possible, Quicksort: no, quadratic time in worst case. not practical Heapsort: yes 
 
 Bottom line. Heapsort is optimal for both time and space, but: Inner loop longer than quicksort’s. Makes poor use of cache. Not stable. can be improved using advanced caching tricks 47Introsort Goal. As fast as quicksort in practice; n log n worst case, in place. 
 Introsort. Run quicksort. Cutoff to heapsort if stack depth exceeds 2 lg n. Cutoff to insertion sort for n = 16. 
 
 
 
 
 
 
 
 
 In the wild. C++ STL, Microsoft .NET Framework. 48Sorting algorithms: summary inplace stable best average worst remarks 2 2 2 selection ✔ ½ n ½ n ½ n n exchanges use for small n 2 2 insertion ✔ ✔ n ¼ n ½ n or partially ordered tight code; 3/2 shell ✔ n log n c n 3 subquadratic n log n guarantee; merge ✔ ½ n lg n n lg n n lg n stable improves mergesort timsort ✔ n n lg n n lg n when preexisting order n log n probabilistic guarantee;
 2 quick ✔ n lg n 2 n ln n ½ n fastest in practice improves quicksort
 2 3way quick ✔ n 2 n ln n ½ n when duplicate keys n log n guarantee;
 heap ✔ 3 n 2 n lg n 2 n lg n inplace holy sorting grail ✔ ✔ n n lg n n lg n 492.4 PRIORITY QUEUES API and elementary implementations ‣ binary heaps ‣ heapsort ‣ Algorithms eventdriven simulation ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.eduMolecular dynamics simulation of hard discs Goal. Simulate the motion of n moving particles that behave
 according to the laws of elastic collision. 51Molecular dynamics simulation of hard discs Goal. Simulate the motion of n moving particles that behave
 according to the laws of elastic collision. Hard disc model. Moving particles interact via elastic collisions with each other and walls. Each particle is a disc with known position, velocity, mass, and radius. No other forces. 
 
 temperature, pressure,
 motion of individual
 
 diffusion constant atoms and molecules 
 Significance. Relates macroscopic observables to microscopic dynamics. MaxwellBoltzmann: distribution of speeds as a function of temperature. Einstein: explain Brownian motion of pollen grains. 52Warmup: bouncing balls Timedriven simulation. n bouncing balls in the unit square. public class BouncingBalls java BouncingBalls 100 public static void main(String args) int n = Integer.parseInt(args0); Ball balls = new Balln; for (int i = 0; i n; i++) ballsi = new Ball(); while(true) StdDraw.clear(); for (int i = 0; i n; i++) ballsi.move(0.5); ballsi.draw(); StdDraw.show(50); main simulation loop 53Warmup: bouncing balls 
 public class Ball 
 private double rx, ry; // position 
 private double vx, vy; // velocity private final double radius; // radius 
 public Ball(...) check for collision with walls / initialize position and velocity / 
 
 public void move(double dt) 
 if ((rx + vxdt radius) (rx + vxdt 1.0 radius)) vx = vx; 
 if ((ry + vydt radius) (ry + vydt 1.0 radius)) vy = vy; rx = rx + vxdt; 
 ry = ry + vydt; 
 public void draw() 
 StdDraw.filledCircle(rx, ry, radius); 
 
 Missing. Check for balls colliding with each other. Physics problems: when what effect CS problems: which object does the check too many checks 54Timedriven simulation Discretize time in quanta of size dt. Update the position of each particle after every dt units of time,
 and check for overlaps. If overlap, roll back the clock to the time of the collision, update the velocities of the colliding particles, and continue the simulation. t t + dt t + 2 dt
 t + Δt
 (collision detected) (roll back clock) 55Timedriven simulation Main drawbacks. 2 n / 2 overlap checks per time quantum. Simulation is too slow if dt is very small. dt too small: excessive computation May miss collisions if dt is too large.
 (if colliding particles fail to overlap when we are looking) dt too large: may miss collisions dt too small: excessive computation dt too large: may miss collisions Fundamental challenge for timedriven simulation 56 Fundamental challenge for timedriven simulationEventdriven simulation Change state only when something interesting happens. Between collisions, particles move in straightline trajectories. Focus only on times when collisions occur. Maintain PQ of collision events, prioritized by time. Delete min = get next collision. 
 Collision prediction. Given position, velocity, and radius of a particle,
 when will it collide next with a wall or another particle 
 Collision resolution. If collision occurs, update colliding particle(s) according to laws of elastic collisions. prediction (at time t) particles hit unless one passes intersection point before the other arrives (see Exercise 3.6.X) resolution (at time t + dt) velocities of both particles change after collision (see Exercise 3.6.X) Predicting and resolving a particleparticle collision 57Particlewall collision Collision prediction and resolution. Particle of radius s at position (rx, ry). Particle moving in unit box with velocity (vx, vy). Will it collide with a vertical wall If so, when s resolution (at time t + dt) velocity after collision = ( − v , v ) x y position after collision = ( 1 − s , r + v dt) y y prediction (at time t) dt time to hit wall wall at (r , r ) = distance/velocity x y x = 1 = (1 − s − r )/v x x v y v x 1 − s − r x Predicting and resolving a particlewall collision 58Particleparticle collision prediction Collision prediction. Particle i: radius s , position (rx , ry ), velocity (vx , vy ). i i i i i Particle j: radius s , position (rx , ry ), velocity (vx , vy ). j j j j j Will particles i and j collide If so, when (vx ', vy ') i i (vx ', vy ') j j m i s i (vx , vy ) i i (rx , ry ) i i (rx ', ry ') i i i time = t time = t + Δt (vx , vy ) j j σ j j 59Particleparticle collision prediction Collision prediction. Particle i: radius s , position (rx , ry ), velocity (vx , vy ). i i i i i Particle j: radius s , position (rx , ry ), velocity (vx , vy ). j j j j j Will particles i and j collide If so, when B7 v · r 0, B7 d0, t= v · r + d Qi2`rBb2 v · v 2 2 d=(∆ v ·∆ r) − (∆ v ·∆ v)(∆ r ·∆ r − s ),s= s + s i j 2 2 Δv⋅Δv = (Δvx) + (Δvy) Δv = (Δvx, Δvy) = (vx −vx , vy −vy ) i j i j 2 2 Δr ⋅Δr = (Δrx) + (Δry) Δr = (Δrx, Δry) = (rx −rx , ry −ry ) i j i j Δv⋅Δr = (Δvx)(Δrx)+ (Δvy)(Δry) € € Important note: This is physics, so we won’t be testing you on it € 60 € € Particleparticle collision resolution Collision resolution. When two particles collide, how does velocity change " " vx = vx + Jx / m vx = vx + Jx / m i i i i i i " " vy = vy + Jy / m vy = vy + Jy / m Newton's second law
 i i i i i i (momentum form) " " vx = vx − Jx / m vx = vx − Jx / m j j j j j j " " vy = vx − Jy / m vy = vx − Jy / m j j j j j j € € J rx J ry 2m m ( v · r) i j Jx= ,Jy = ,J = s s s(m +m ) i j impulse due to normal force
 (conservation of energy, conservation of momentum) Important note: This is physics, so we won’t be testing you on it 61Particle data type skeleton public class Particle private double rx, ry; // position private double vx, vy; // velocity private final double radius; // radius private final double mass; // mass private int count; // number of collisions public Particle( ... ) ... public void move(double dt) ... public void draw() ... public double timeToHit(Particle that) predict collision public double timeToHitVerticalWall() with particle or wall public double timeToHitHorizontalWall() public void bounceOff(Particle that) resolve collision public void bounceOffVerticalWall() with particle or wall public void bounceOffHorizontalWall() http://algs4.cs.princeton.edu/61event/Particle.java.html 62Collision system: eventdriven simulation main loop two particles on a collision course Initialization. Fill PQ with all potential particlewall collisions. Fill PQ with all potential particleparticle collisions. 
 third particle interferes: no collision “potential” since collision is invalidated 
 if some other collision intervenes 
 
 
 An invalidated event Main loop. Delete the impending event from PQ (min priority = t). If the event has been invalidated, ignore it. Advance all particles to time t, on a straightline trajectory. Update the velocities of the colliding particle(s). Predict future particlewall and particleparticle collisions involving the colliding particle(s) and insert events onto PQ. 63Event data type Conventions. Neither particle null ⇒ particleparticle collision. One particle null ⇒ particlewall collision. Both particles null ⇒ redraw event. private static class Event implements ComparableEvent private final double time; // time of event private final Particle a, b; // particles involved in event private final int countA, countB; // collision counts of a and b public Event(double t, Particle a, Particle b)
 create event ... public int compareTo(Event that) ordered by time return this.time that.time; public boolean isValid()
 valid if no intervening collisions (compare collision counts) ... 64Particle collision simulation: example 1 java CollisionSystem 100 65Particle collision simulation: example 2 java CollisionSystem billiards.txt 66Particle collision simulation: example 3 java CollisionSystem brownian.txt 67Particle collision simulation: example 4 java CollisionSystem diffusion.txt 68
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.BenjaminClark
User Type:
Teacher
Country:
United States
Uploaded Date:
21-07-2017