Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I don't think the <a href="http://en.cppreference.com/w/cpp/container/priority_queue"><code>std::priority_queue</code></a> class allows for an efficient implementation of <code>decrease-key</code> style operations.</p> <p>I rolled my own binary heap based data structure that supports this, bascially along very similar lines to what you've described for the <code>std::set</code> based priority queue you have:</p> <ul> <li>Maintain a binary heap, sorted by <code>value</code> that stores elements of <code>pair&lt;value, ID&gt;</code> and an array that maps <code>ID -&gt; heap_index</code>. Within the heap routines <code>heapify_up, heapify_down</code> etc it's necessary to ensure that the mapping array is kept in-sync with the current heap position of elements. This adds some extra <code>O(1)</code> overhead.</li> <li>Conversion of an array to a heap can be done in <code>O(N)</code> according to the standard algorithm described <a href="http://en.wikipedia.org/wiki/Binary_heap">here</a>. </li> <li>Peeking at the root element is <code>O(1)</code>.</li> <li>Checking if an <code>ID</code> is currently in the heap just requires an <code>O(1)</code> look-up in the mapping array. This also allows <code>O(1)</code> peeking at the element corresponding to any <code>ID</code>.</li> <li><code>Decrease-key</code> requires an <code>O(1)</code> look-up in the mapping array followed by an <code>O(log(N))</code> update to the heap via <code>heapify_up, heapify_down</code>.</li> <li>Pushing a new item onto the heap is <code>O(log(N))</code> as is popping an exitsing item from the heap.</li> </ul> <p>So asymptotically the runtime is improved for a few of the operations compared with the <code>std::set</code> based data structure. Another important improvment is that binary heaps can be implemented on an array, while binary trees are node-based containers. The extra data locality of the binary heap usually translates to improved runtime. </p> <p>A few issues with this implementation are:</p> <ul> <li>It only allows integer item <code>ID</code>'s.</li> <li>It assumes a tight distribution of item <code>ID</code>'s, starting at zero (otherwise the space complexity of the mapping array blows up!).</li> </ul> <p>You could potentially overcome these issues if you maintained a mapping hash-table, rather than a mapping array, but with a little more runtime overhead. For my use, integer <code>ID</code>'s have always been enough.</p> <p>Hope this helps.</p>
    singulars
    1. This table or related slice is empty.
    1. POEasiest way of using min priority queue with key update in C++
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USDarren Engwirda
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks! Your method agrees with those described in textbooks, and I believe it has optimal performance. Since in practice we have to maintain the ID --> heap_index array, I guess there is no better way than implementing our own binary heap that can achieve the same performance as yours?
      singulars
      1. PO
      1. USChong Luo
    2. CO@ChongLuo: Since the mapping array needs to be updated within the `heapify` routines I don't think you can use the `std::` routines, I think you need to write you're own. If you were really looking for "the fastest" priority queue for algorithms like Dijkstra's etc it may also be worth checking out some related data structures: Brodal queues, Fibonacci heaps, n-ary heaps, 2-3 heaps to name a few. Some of these data structures are very complex, but offer theoretical improvements to asymptotic complexity...
      singulars
      1. PO
      1. USDarren Engwirda
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload