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 >>