A Bit About Dijkstra’s

Some Basics

Priority Queues

  • A priority queueis a data structure for maintaining a set S of elements, each with an associated value called a key.
  • A min-priority queue supports the following operations.
    • INSERT(S, x) inserts the element x into the set S. This operation could be written as S = S ∪ {x}.
    • MINIMUM(S) returns the element of S with the smallest key.
    • EXTRACT-MIN(S)removes and returns the element of S with the smallest key.
    • DECREASE-KEY(S, x, k) decreases the value of element x’s key to the new value k, which is assumed to be at least as small as x’s current key

Pages:Contents<< Previous 3 Next Page >>

One Comment Add yours

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.