Data Structures and Algorithms

Priority Queue: Tips on when to choose priority queue as the data structure: Ref: http://stackoverflow.com/questions/18049847/when-would-i-use-a-priority-queue

1. Event-driven simulation: customers in a line, colliding particles

2. Numerical computation: reducing roundoff error

3. Data compression. Huffman codes which compresses data.

4. Graph searching: Dijkstra's algorithm, Prim's algorithm

5. Number theory: sum of powers

6. Artificial intelligence: A* search

7. Statistics: maintain largest M values in a sequence

8. Operating systems: load balancing, interrupt handling Discrete optimization. bin packing, scheduling Spam filtering. Bayesian spam filter

9. Finding top items: N busiest network connections, N most valuable customers, N largest disk users

Important points on graph search:

1. We typically use BFS orDFS search to explore graphs. BFS uses a Queue() data structure to store all the neighboring nodes and explores them in a FIFO order. DFS on the other hand uses a Stack() data structure to go deeper to store all the nodes and then explore them in a LIFO order.

2. In Dijkstra or in A* search this needs to change.

   1. The Graph now needs to know the the cost of selecting the next node.

   2. We cannot use simple Queue any more, since we have to associate some kind of priority to each of the neighboring nodes and pick the next node based on that priority. So we change our data structure choice from Queue() to priority queue()

   3. The search now needs to figure out this cost and build the priority queue based on this information