The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Earlier, I described the Kruskal’s algorithm to find the MST in time O(E log V). Prim’s algorithm is another greedy algorithm that finds an MST in time O(E log V). The difference is that the Prim’s algorithm grows an MST, starting from a single vertex, always adding the least-cost edge from a tree vertex to a non-tree vertex to the current set of edges in the MST.

# Monthly Archives: May 2013

# Indexed Min-Priority Queue C++ implementation

A min-priority queue is an abstract data structure that supports efficient query of the minimum element in a list of elements, insertion of elements and deletion of the minimum element. It can be implemented as a min-heap, providing access to the minimum element in O(1), deletion of the minimum element in O(log N) and insertion in O(log N) where N is the number of elements in the heap.

# Kruskal’s Minimum Spanning Tree Algorithm

The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Kruskal’s algorithm finds the MST in time O(E log V). It is a greedy algorithm that always tries to add the next least-cost edge to the current set of edges in the MST if its addition does not create a cycle in the MST.

# Counting inversions in an array

The problem is to count the number of inversions in an array. Two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

For example, the sequence 1, 20, 6, 4, 5 has five inversions (20, 6), (20, 4), (20, 5), (6, 4) and (6, 5).

# Randomized selection algorithm

The problem is to find the i^{th} order statistic (i.e., i^{th} smallest element) in an input array. This algorithm is a modification of quicksort and takes time O(n), on average, on an input array of size n.