title: Dijkstra algorithm. Min heap as a min-priority queue
body: <p>I'm reading about Dijkstra's algorithm in <em>CLRS, Third Edition</em> (p. 662). Here is a part from the book I don't understand:</p>
  
  <blockquote>
    <p>If the graph is sufficiently sparse — in particular, <code>E = o(V^2/lg V)</code> — we can improve the algorithm by implementing the min-priority queue with a binary min-heap.</p>
  </blockquote>
  
  <p>Why should the graph be sparse?</p>
  
  <hr>
  
  <p>Here is another part:</p>
  
  <blockquote>
    <p>Each DECREASE-KEY operation takes time <code>O(log V)</code>, and there are still
    at most E such operations.</p>
  </blockquote>
  
  <p>Suppose my graph looks like this:</p>
  
  <p><a href="https://i.stack.imgur.com/rCurN.jpg"><img src="https://i.stack.imgur.com/rCurN.jpg" alt="From 1 to 6"></a></p>
  
  <p>I'd like to calculate the shortest path from 1 to 6 and use the min-heap approach. So first off, I add all my nodes to a min priority queue. After building a min heap, the min node is the source node (since its distance to itself is 0). I extract it and update distances of all its neighbors. </p>
  
  <p>Then I need to call <code>decreaseKey</code> on the node with the lowest distance to make a new minimum of the heap. But how do I know its index in constant time? </p>
  
  <p><strong>Node</strong></p>
  
  <pre><code>private static class Node implements Comparable&lt;Node&gt; {
  
      final int key;
      int distance = Integer.MAX_VALUE;
      Node prev = null;
  
      public Node(int key) {
          this.key = key;
      }
  
      @Override
      public int compareTo(Node o) {
          if (distance &lt; o.distance) {
              return -1;
          } else if (distance &gt; o.distance) {
              return 1;
          } else {
              return 0;
          }
      }
  
      @Override
      public String toString() {
          return "key=" + key + " distance=" + distance;
      }
  
      @Override
      public int hashCode() {
          return key;
      }
  
      @Override
      public boolean equals(Object obj) {
          if (this == obj) {
              return true;
          }
          if (!(obj instanceof Node)) {
              return false;
          }
          Node other = (Node) obj;
          return key == other.key;
      }
  }
  </code></pre>
  
  <p><strong>MinPriorityQueue</strong></p>
  
  <pre><code>public static class MinPriorityQueue {
  
      private Node[] array;
      private int heapSize;
  
      public MinPriorityQueue(Node[] array) {
          this.array = array;
          this.heapSize = this.array.length;
      }
  
      public Node extractMin() {
          Node temp = array[0];
          swap(0, heapSize - 1, array);
          heapSize--;
          sink(0);
          return temp;
      }
  
      public boolean isEmpty() {
          return heapSize == 0;
      }
  
      public void buildMinHeap() {
          for (int i = heapSize / 2 - 1; i &gt;= 0; i--) {
              sink(i);
          }
      }
  
      public void decreaseKey(int index, Node key) {
          if (key.compareTo(array[index]) &gt;= 0) {
              throw new IllegalArgumentException("the new key must be greater than the current key");
          }
          array[index] = key;
          while (index &gt; 0 &amp;&amp; array[index].compareTo(array[parentIndex(index)]) &lt; 0) {
              swap(index, parentIndex(index), array);
              index = parentIndex(index);
          }
      }
  
      private int parentIndex(int index) {
          return (index - 1) / 2;
      }
  
      private int left(int index) {
          return 2 * index + 1;
      }
  
      private int right(int index) {
          return 2 * index + 2;
      }
  
      private void sink(int index) {
          int smallestIndex = index;
          int left = left(index);
          int right = right(index);
          if (left &lt; heapSize &amp;&amp; array[left].compareTo(array[smallestIndex]) &lt; 0) {
              smallestIndex = left;
          }
          if (right &lt; heapSize &amp;&amp; array[right].compareTo(array[smallestIndex]) &lt; 0) {
              smallestIndex = right;
          }
          if (index != smallestIndex) {
              swap(smallestIndex, index, array);
              sink(smallestIndex);
          }
      }
  
      public Node min() {
          return array[0];
      }
  
      private void swap(int i, int j, Node[] array) {
          Node temp = array[i];
          array[i] = array[j];
          array[j] = temp;
      }
  
  }
  </code></pre>