DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

A Priority Queue Based on Message Priority and Time Elapsed

This tutorial explains how to design a custom queue that will pop out a message with the highest priority.

Shruthi MS user avatar by
Shruthi MS
·
Aug. 16, 18 · Tutorial
Like (3)
Save
Tweet
Share
5.19K Views

Join the DZone community and get the full member experience.

Join For Free

Problem:

The aim is to design a custom queue that will pop out a message with the highest priority. Each input message has an already assigned priority value, although this isn’t a fixed value. The priority of each message is incremented after a fixed amount of time has passed.

Solution:

Let's assume that there are a total of 5 different priority levels. 1 to 5, with 1 being the lowest and 5 being the highest. For every 10 minutes a message spends inside the queue, the priority is bumped up by 1 unit. The maximum priority value that can be assigned is 5. In case two elements have the same priority, the messages that have spent the longest in the queue should be popped out first.

A linked list can be used to store the incoming messages. A new message is always added to the end of the list.

To find the element with the highest priority, we need to find an element with the highest summation value of initial priority and time elapsed increments.

The queue would look something like this:

Image title

Use a pointer to refer to the first occurrence of every type of message, Like so:

Image title

These 4 messages are possible candidates for the message with the highest priority.

Now we have to take time elapsed into consideration and increment accordingly. For this, we can ignore all the lesser priority messages that occur after the one we have already calculated. That is, we can skip message 3 and message 2 because message 4 will always be older and will have a higher increment.

We will only have to calculate it for 4 and 5.

Image title

Case 1: If 4 hasn’t spent a full 10 mins in the queue, the element to be popped out is 5

Case 2: If 4 has spent over 10 mins in the queue, the element to be popped out is 4. Even though the final values of both messages are equal, message 4 is popped out because it is ahead of message 5 in the linked list.

Once a certain message type is pushed out, the pointer is moved to the next occurrence of that message type.

Element Pointer (computer programming) Design

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • Upgrade Guide To Spring Data Elasticsearch 5.0
  • The Role of Data Governance in Data Strategy: Part II
  • How To Avoid “Schema Drift”
  • The Changing Face of ETL

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: