Data Structures, Algorithms, & Applications in Java
Chapter 18, Exercise 35

We need to perform the following operations on the d values: select the as yet unselected vertex with minimum d value, decrease some distance values. These operations are done fairly efficiently using a min heap which is augmented by an array location to keep track of the location in heap[] of the distance value of a vertex. Therefore, we begin by defining the class ModifiedMinHeap. The invocation decreaseWeight(x) replaces the old distance (weight) of vertex x.vertex by the smaller value x.weight. The method initialize has not been implemented. Although the code given below stores weighted edge nodes in the min heap, it is sufficient to store only the weights. 
public class ModifiedMinHeap
{
   // data members
   WeightedEdgeNode [] heap;   // array for complete binary tree
   int [] location;            // current location of an element
   int size;                   // number of elements in heap

   // constructors
   /** create a heap with the given initial capacity */
   public ModifiedMinHeap(int initialCapacity)
   {
      if (initialCapacity < 1)
         throw new IllegalArgumentException
                   ("initialCapacity must be >= 1");
      heap = new WeightedEdgeNode [initialCapacity + 1];
      location = new int [initialCapacity + 1];
      size = 0;
   }
   
   /** create a heap with initial capacity 10 */
   public ModifiedMinHeap()
      {this(10);}

   // methods
   /** @return true iff the heap is empty */
   public boolean isEmpty()
      {return size == 0;}

   /** @return number of elements in the heap */
   public int size()
      {return size;}

   /** @return minimum element
     * @return null if the heap is empty */
   public WeightedEdgeNode getMin()
   {
      if (size == 0)
         return null;
      else
         return heap[1];
   }

   /** put theElement into the heap */
   public void put(WeightedEdgeNode theElement)
   {
      // increase array size if necessary
      if (size == heap.length - 1)
         heap = (WeightedEdgeNode []) ChangeArrayLength.changeLength1D
                                    (heap, 2 * heap.length);
   
      // find place for theElement
      // i starts at new leaf and moves up tree
      int i = ++size;
      while (i != 1 && ((Comparable) heap[i/2].weight)
                         .compareTo(theElement.weight) > 0)
      {
         // cannot put theElement in heap[i]
         heap[i] = heap[i/2]; // move element down
         location[heap[i].vertex] = i;
         i /= 2;              // move to parent
      }
   
      heap[i] = theElement;
      location[theElement.vertex] = i;
   }
   
   /** remove min element and return it */
   public WeightedEdgeNode removeMin()
   {
      // if heap is empty return null
      if (size == 0) return null;       // heap empty
   
      WeightedEdgeNode x = heap[1];           // min element
      location[x.vertex] = 0;
   
      // restucture heap
      WeightedEdgeNode y = heap[size--];      // last element
   
      // find place for y starting at root
      int i = 1,  // current node of heap
          ci = 2; // child of i
      while (ci <= size)
      {
         // heap[ci] should be smaller child of i
         if (ci < size && ((Comparable) heap[ci].weight)
                            .compareTo(heap[ci+1].weight) > 0)
                               ci++;
   
         // can we put y in heap[i]?
         if (((Comparable) y.weight).compareTo(heap[ci].weight) <= 0)
            break;   // yes
   
         // no
         heap[i] = heap[ci];             // move child up
         location[heap[i].vertex] = i;
         i = ci;                         // move down a level
         ci *= 2;
      }
      heap[i] = y;
      location[y.vertex] = i;
   
      return x;
   }
   

   /** decrease weight of x.vertex to x.weight */
   public void decreaseWeight(WeightedEdgeNode x)
   {
      // check if x.vertex in heap
      if (location[x.vertex] == 0)
         // not in heap
         throw new IllegalArgumentException
                   ("illegal id value");
   
      // make sure new distance is smaller
      if (((Comparable) x.weight)
            .compareTo(heap[location[x.vertex]].weight) >= 0)
         throw new IllegalArgumentException
           ("new distance value must be less than old one");
   
      // find new place for x
      // i starts at old location of x and moves up tree
      int i = location[x.vertex];
      while (i != 1 && ((Comparable) x.weight)
                         .compareTo(heap[i/2].weight) < 0)
      {// cannot put x in heap[i]
         heap[i] = heap[i/2];              // move element down
         location[heap[i].vertex] = i;
         i /= 2;                           // move to parent
      }
      heap[i] = x;
      location[x.vertex] = i;
   }
}


The shortest paths code now takes the form given below. 
public class LinkedWDigraphWithShortestPaths2 extends LinkedWDigraph
{
   // constructors
   public LinkedWDigraphWithShortestPaths2(int theVertices)
      {super(theVertices);}
   
   // default is a 0 vertex graph
   public LinkedWDigraphWithShortestPaths2()
      {this(0);}


   /** find shortest paths from vertex s
     * @return shortest distances in d
     * @return predecessor information in p */
   public void shortestPathsUsingAHeap(int s, Operable [] d, int [] p)
   {
      if (s < 1 || s > n)
         throw new IllegalArgumentException
                   ("source vertex cannot be " + s);

      ModifiedMinHeap heap = new ModifiedMinHeap(); // min heap of d values
            // for reachable vertices for which a path is yet to be generated
     
      // initialize d, p, and l
      // first set all d values to null and all p values to -1
      for (int i = 1; i <= n; i++)
      {
          d[i] = null;
          p[i] = -1;
      }
      // now change d and p values for vertices adjacent from s
      Iterator is = aList[s].iterator();
      while (is.hasNext())
      {
         WeightedEdgeNode wNode = (WeightedEdgeNode) is.next();
         d[wNode.vertex] = (Operable) wNode.weight;
         d[s] = (Operable) ((Operable) wNode.weight).zero();
         p[wNode.vertex] = s; 
         heap.put(new WeightedEdgeNode(wNode.vertex, d[wNode.vertex]));
      }
      p[s] = 0;  // source vertex has no predecessor
   
      // update d and p
      while (!heap.isEmpty())
      {// more paths exist
         // extract vertex v with least d from the min heap
         int v = ((WeightedEdgeNode) heap.removeMin()).vertex;
   
         // next shortest path is to vertex v
         // update d values
         Iterator iv = aList[v].iterator();
         while (iv.hasNext())
         {
            WeightedEdgeNode wNode = (WeightedEdgeNode) iv.next();
            int j = wNode.vertex;
      	    if (p[j] == -1 || d[j].compareTo(d[v].add(wNode.weight)) > 0)
            {
               // d[j] decreases
               d[j] = (Operable) d[v].add(wNode.weight);
               // add j to heap if not already there, else update heap entry
               if (p[j] == -1)
                  // j is not in the min heap
                  heap.put(new WeightedEdgeNode(j, d[j]));
               else
                  // j is in the min heap
                  heap.decreaseWeight(new WeightedEdgeNode(j, d[j]));
               p[j] = v;
            }
         }
      }
   }
}


Sine the digraph has O(n) edges, the time spent performing heap operations is O(n log n), and the time spent in the remainder of the code is O(n + e) = O(n). So, the overall complexity is O(n log n).