Priority Queue in Data Structure: Quiz and Flashcards

Study Notes

Priority Queue Abstract Data Type

A priority queue is an abstract data type similar to a regular queue or stack data structure.
Each element in a priority queue has an associated priority.

Priority Scheduling

Elements with high priority are served before elements with low priority.
In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued.
In other implementations, the order of elements with the same priority is undefined.

Implementation

Priority queues can be implemented using heaps, but they are conceptually distinct from heaps.
A priority queue can be implemented with a heap or another method such as an ordered array.
Implementation is similar to a list or a map, which can be implemented with a linked list or an array.

Operations

A priority queue must at least support the following operations:
- is_empty: check whether the queue has no elements.
- insert_with_priority: add an element to the queue with an associated priority.
- pull_highest_priority_element: remove the element from the queue that has the highest priority, and return it.
Some implementations may reverse the order of priorities, considering lower values to be higher priority.

Additional Operations

peek_at_highest_priority_element: returns the highest-priority element but does not modify the queue.
delete_element: removes the highest-priority element from the queue.
pull_lowest_priority_element: removes the element from the queue that has the lowest priority, and returns it.
inspecting the first few highest- or lowest-priority elements: returns the highest- or lowest-priority elements but does not modify the queue.
clearing the queue: removes all elements from the queue.
clearing subsets of the queue: removes specific elements from the queue.
performing a batch insert: adds multiple elements to the queue at once.
merging two or more queues into one: combines elements from multiple queues into one.
incrementing priority of any element: increases the priority of a specific element.

Relationship with Stacks and Queues

Stacks and queues can be implemented as particular kinds of priority queues.
In a stack, the priority of each inserted element is monotonically increasing.
In a queue, the priority of each inserted element is monotonically decreasing.

Description

Test your understanding of priority queues, a data structure that serves elements based on their priority. Learn how elements with high priority are served before those with low priority. Explore implementation variations and their effects on queue ordering.