Live briefing
Everything about Priority queue
Abstract data type in computer science
In computer science, a priority queue is an abstract data type similar to a regular queue where each element has an associated priority determining its order of service. Priority queue serves highest priority items first. Priority values have to be instances of an ordered data type, and higher priority can be given either to the lesser or to the greater values with respect to the given order relation. For example, in the Java standard library, the PriorityQueue class considers the lowest element with respect to their order as having the highest priority. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Priority queueA 5-minute orientation
- Skim a recent paper: A multi‐queue priority‐based task scheduling algorithm in fog computing environmentInfluential work since 2022
- Pick up a classic book: Data structures and algorithms in JavaThe most-reprinted book on the subject
- Read the landmark paper: Optimal Incentive-Compatible Priority Pricing for the M/M/1 QueueCited 461 times
- Go sideways: Heap (data structure)A closely related topic
- Go sideways: Binary heapA closely related topic
📖 Definitions
Noun An abstract data type similar to a regular queue or stack abstract data type.
🏆 Landmark papers (most cited)
Optimal Incentive-Compatible Priority Pricing for the M/M/1 Queue
A priority queue in which initialization and queue operations takeO(loglogD) time
A single server priority queue with server failures and queue flushing
Preemptive Resume Priority Queue
Parallel heap: An optimal parallel priority queue
A Priority Queue with Discounted Linear Costs
A two-queue, one-server model with priority for the longer queue
The Nonpreemptive Priority MAP/G/1 Queue
🆕 Influential since 2022
A multi‐queue priority‐based task scheduling algorithm in fog computing environment
Clustering Based Priority Queue Algorithm for Spatial Task Assignment in Crowdsourcing
A fog-assisted information model based on priority queue and clinical decision support systems
An active queue management for wireless sensor networks with priority scheduling strategy
Preemptive Priority Markovian Queue Subject to Server Breakdown with Imperfect Coverage and Working Vacation Interruption
📚 Books worth reading
Data structures and algorithms in JavaMichael T. Goodrich, Roberto Tamassia · 2001
Data structures and algorithm analysis in CMark Allen Weiss · 1993- 📕IEEE Standards for Local and Metropolitan Area NetworksInstitute of Electrical and Electronics Engineers · 1993
Probability, statistics, and queueing theoryArnold O. Allen · 1978
Mastering algorithms with CKyle Loudon, Andy Oram · 1999
Queueing AnalysisHideaki Takagi · 1991- 📕PICADY2Marie C. Semmens · 1985
- 📕Some contributions to the theory of priority queuesPeter Dunbar Welch · 1963
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Heap (data structure) In computer science, a heap is a tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is the parent node…
- Binary heap A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary…
- Binomial heap In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap)…
- Double-ended priority queue In computer science, a double-ended priority queue (DEPQ) or double-ended heap or priority deque is a data structure similar to a priority queue or heap…
- Fibonacci heap In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better…
- Pairing heap A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael…
- Queap In computer science, a queap is a priority queue data structure. The data structure allows insertions and deletions of arbitrary elements, as well as retrieval…
- Treap In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain…