Princeton Alogorithm COS226 Week
now in before lecture, we already have a concept about stack, queue, randomized queue. we also learn some sorting algorithm, selection sort, insertion sort, shell sort, merge sort, quick sort.
is there a data structure could combine them all.
i mean i want to get a element by order one by one.
this is today's topic. priority queue, below is the API
image.png
there are a lot of application used this data structure. in the later lecture, a famous shortest path called Dijkstra use it. and in operating system, load balancing use it. data compression will use it. event driven simulation will use it.
the find first kth problem is a traditional problem using priority queue. we have a log with a lot of transaction, please find the most biggest 3 transaction. we have not enough memory to store all of them. how to solve it?
image.png
we can maintain a priority queue with 3 items. if there is a item larger than the min of the queue, then replace the min.
image.png
how the priority queue implemented?
before introduce it, we want to introduce a concept of complete tree.
image.png
and binary heap could use this structure to work. we only keep a array. the left children is 2 * i. the right children is 2 * i + 1. when the root index is 1.
image.png
in heap there are two important operation.
promotion and demotion.
promotion
when child's key becomes larger key than its parent's key
image.png
image.png
demotion
parent's key becomes smaller than one of its children's
image.png
image.png
below is some important binary heap consideration
the key should be immutable because change key while they are on the PQ, will break the PQ characteristics.
in java we can use final to make the class immutable.
image.png
there are a lot of advantages of immutable class.
simplifies debugging, safer in presence of hostile code, simplifies concurrent programming, safe to use as key in priority queue or symbol table.
Heap sort
so now we get a data structure which could pop element by order in log n time.
so we get another sort algorithm with n lg n in place.
the basic plan for it is
create max-heap with all N keys, then repeatedly remove the max one.
a important thing is heap construction, we should build the heap from bottom to top, then we can get O (n) time to build the heap.
image.png
image.png
the most difference of heap sort it a inplace sorting algorithm with N log N worst-case
but the disadvantages is that
inner loop longer than quicksort, make poor use of cache memory, not stable.
image.png
Molecular dynamics simulation
image.png
image.png
the solution is event-driven simulation.
change state only when something happen.
we now only focus on times when collisions occur. maintain PQ of collision events, prioritized by time.
remove the min = get next collision
image.png
QUIZ
Q1
image.png
this question could be solved by two priority queue, one is maxheap, another is minheap.
because we need to find the median in constant time, we need to balance the elements evenly into two pq. the most important is that maxHeap.max <= minHeap.min
then the maxHeap max is the median.
the problem now is remove and insert, when insert we can insert to the max heap first, then check it still meet the invariant, the size diff is <= 1, and maxHeap max <= minHeap min, if not, do some balance action.
remove we can just pop the maxHeap max, then check invariant and do balance.
Q2
image.png
because we know the priority queue is the array strucutre, we can know the size of it, and random a number in size, then just the arr[idx]
delRandom, will think more, we need to delete a value in the middle. we random a position and then swap with the array last one, the important thing here is we don't know the key is should promotion or demotion, so we need try both.
Q3
image.png
version 1 could be prepare all the a^3 + b^3 pair result, then sort them.
we can know the result are same is neighbor, if there are more than 1 number in the list, this is taxicab number
version 2 , we could use priority queue. the record 1 ~ n-1's pair, pair contains two number, one is a and another is b, pair 1's first number always is 1, second number can be combined with any number large than 1. same as others pair k.
so now we pop the min, check it is same as previous, if it is, we find a tax number. if not, we increase second number in pair.
Project 8 Puzzle
image.png
this project have no bonus, but the 100% score code when run the PuzzleChecker, it will cause
Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
at Board.neighbor(Board.java:126)
at Board.neighbors(Board.java:139)
at Solver.<init>(Solver.java:57)
at PuzzleChecker.main(PuzzleChecker.java:52)
the project with Puzzle check download link
https://coursera.cs.princeton.edu/algs4/assignments/8puzzle/8puzzle.zip
so i do the improvement below
Use a 1d array instead of a 2d array (as suggested above).
Cache either the Manhattan distance of a board (or Manhattan priority of a search node). It is waste to recompute the same quantity over and over again.
Exploit the fact that the difference in Manhattan distance between a board and a neighbor is either −1 or +1.
Use only one PQ to run the A* algorithm on the initial board and its twin.
When two search nodes have the same Manhattan priority, you can break ties however you want, e.g., by comparing either the Hamming or Manhattan distances of the two boards.
Use a parity argument to determine whether a puzzle is unsolvable (instead of two synchronous A* searches). However, this will either break the API or will require a fragile dependence on the toString() method, so don't do it.
after improved above suggestion, the speed is very faster, we can solve all the example except 4x4-50, 4x4-78, 4x4-80 with in 75 seconds.
image.png
the good blog for it is
https://medium.com/breathe-publication/solving-the-15-puzzle-e7e60a3d9782
how to check solvable in n^2
http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
if u want to improve more please reference this github.
https://blog.csdn.net/Wood_Du/article/details/89666736
https://github.com/jDramaix/SlidingPuzzle
course quiz and project : https://github.com/yixuaz/algorithm4-princeton-cos226
