I am not clear about the IndexMinPQ data structure purpose . An implementation is given IndexMinPQ.java .
Although book itself provide brief introduction but not clear . I am not clear why we needed this data structure and other operations?
The problem with heap implementation of a priority queue is that it's difficult to find a particular node. For example, suppose you have a heap with 100,000 items in it, and you want to decrease the priority of a node that has the value 732. The only way you can find that node is through a linear search of the heap. Decreasing the priority of the node is an O(log n) operation, but finding the node is O(n).
An indexed priority queue maintains a lookup structure so that you can find the node in O(1).
This ability is important in any system that needs to modify nodes in a priority queue. A job scheduler, for example, in which you frequently need to adjust the priority of jobs, or cancel jobs.