What is a Priority Queue? How is it different from a normal Queue?

0-2 years experience

1. 1Imagine we're building a customer support ticketing system. Right now, tickets are handled in the exact order they arrive. However, we want to make sure 'Enterprise' customers always get their tickets resolved first, regardless of when they submitted them. How would you change our data structure choice to support this, and what happens to the time complexity of adding a new ticket?
2. 2We have a background worker processing image uploads. We want to introduce a 'high-priority' flag for urgent uploads. If you swap out our standard FIFO queue for a priority queue, how does that change how we retrieve the next item to process, and what's a potential downside for the standard uploads?

2-5 years experience

1. 1We recently switched our task scheduler from a simple array-based queue to a binary heap-based priority queue because task volume grew. However, our monitoring shows that low-priority tasks are now sitting in the queue indefinitely and never getting processed. Why is this happening, and how would you modify the priority calculation or the queue structure to fix this 'starvation' issue?
2. 2You're implementing an in-memory message broker for a local microservice. The service needs to process messages based on a dynamic 'urgency' score that changes over time. If you use a standard priority queue, updating the priority of an existing message is highly inefficient. How would you design a data structure or wrapper to allow fast priority updates (decrease-key operations)?

5-8 years experience

1. 1We are designing a highly concurrent, multi-threaded job execution engine where hundreds of worker threads pull tasks from a single shared priority queue. A naive synchronized heap is causing massive lock contention. How would you design or optimize this queue to reduce contention while still maintaining reasonable priority guarantees?
2. 2We need to build a distributed rate-limiter that prioritizes API requests from premium users during traffic spikes. If we use a Redis-backed sorted set as a priority queue, what are the scaling limits, memory implications, and failure modes we need to design around compared to a simple Kafka-style FIFO partition?

8+ years experience

1. 1Our core platform relies on a massive, distributed FIFO message queue (like SQS or Kafka) to process asynchronous transactions. Business stakeholders now demand multi-tenant tiering (Platinum, Gold, Silver) with strict SLA guarantees, meaning Platinum messages must bypass Gold/Silver even during massive backlogs. How do you architect this priority-based routing layer on top of our existing FIFO infrastructure without a complete, high-risk rewrite of our messaging backbone?
2. 2At scale, a global priority queue can introduce severe head-of-line blocking and priority inversion across distributed systems. How would you design a federated scheduling architecture that balances strict priority execution with localized throughput and fault tolerance across multiple geographic regions?