Algorithms in a Nutshell

Principle: Choose the Right Data Structure

The famed algorithm designer Robert Tarjan was once quoted as saying that any problem can be solved in O(n log n) time with the right data structure. Many algorithms need to use a priority queue to store partial progress and direct future computations. One of the most common means of implementing a priority queue is through a binary heap, which allows for O(log n) behavior for removing the element with lowest priority from the priority queue. However, a binary heap offers no ability to determine whether it contains a specific element. We expanded on this very point in the discussion of Line Sweep (Chapter 9), since this algorithm can only provide O(n log n) performance because it uses an augmented binary tree to implement the priority queue and still provides O(log n) performance for removing the minimum element. Another way of stating this principle is to beware of selecting an inappropriate data structure that will prevent an algorithm from achieving its best performance.

Table 11-3 shows the graph algorithms discussed in Chapter 6.

Table 11-3. Chapter 6: Graph algorithms

Algorithm	Best	Average	Worst	Concepts	Page
Depth-first Search	V+E	V+E	V+E	Graph, Array, Recursion, Backtracking	144
Breadth-first Search	V+E	V+E	V+E	Graph, Array, Queue	150
Dijkstra's Algorithm PQ	(V+E) log V	(V+E) log V	(V+E) log V	Weighted Directed Graph, Array, Priority Queue, Overflow	154
Dijkstra's Algorithm DG	V2+E	V2+E	V2+E