title: How to implement O(logn) decrease-key operation for min-heap based Priority Queue?
body: <p>I am working on an application that demonstrates the <em>Djikstra's algorithm</em>, and to use it, I need to restore the heap property when my elements' value is decreased.</p>
  
  <p>The problem regarding the complexity is that <strong>when the algorithm changes the value of an element, that element's index</strong> in the internal structure (heap in this case) used for the priority queue <strong>is unknown</strong>. As such, I currently need to do an O(n) search, in order to recover the index, before I can perform an actual <em>decrease-key</em> on it.</p>
  
  <p>Moreover, I am not exactly sure about the actual code needed for the operation. I am using the D-Heap <a href="http://en.algoritmy.net/article/41909/D-ary-heap" rel="noreferrer">here</a> for my Priority Queue. Pseudocode would help, but I would prefer an example in Java on how this should be done.</p>