0

So, i'm coding one thing on c++, and i'm trying to implement a priority queue with pairing heaps. I want this priority to automatically increase over time, so that if the element (a class) has been in the heap for, say, 5 minutes, it's priority (a variable) is increased. And i have no clue how to make that happen.

I could implement a function which would check the duration for each element each set amount of time, but the problem is that it's pretty tough to check each and every element within a heap. So I think I need to do something withinin the elements, but I'm not sure what and how.

Is there any simple solution to that? I feel like i must be missing something, but if that's not the case, then I'd better drop this idea, because I have to finish this thing pretty soon.

UP: This program is meant for the human queue, so the reason for this idea is to not make people wait for too long. The priority is arbitrary, there are priority "levels" set for each element when it's added, so making the time the priority is not a solution for me.

Noname
  • 85
  • 10
  • 4
    How about just using a timestamp, where the age of that timestamp is the priority? If you want to prioritize elements by how long they've been in the container, you can just use a `queue`. – François Andrieux Feb 23 '18 at 16:18
  • Aside - you probably don't want the 'priority' to be a variable; but a getter function; so that you can change how the priority is done without having to change lots of code – UKMonkey Feb 23 '18 at 16:29
  • http://en.cppreference.com/w/cpp/container/priority_queue – Jesper Juhl Feb 23 '18 at 16:55
  • I don't want to prioritize elements by the time at all, the priority will be more arbitrary, like "levels" of priority set for each element when it's being added. The increase is only needed so that the elements with lower priorities don't stay for too long. – Noname Feb 23 '18 at 17:00

1 Answers1

0

You can add the elements to a linked list:

  1. A new element is added to the end of the list

  2. When the first element is in heap for 5 mins, its priority increased and it is moved to the end of the list.

This way you can check only the first element. Another advantage is that you can set the timer to the value the first element is to be checked in. That is, no need to do unnecessary periodical checks.

freim
  • 596
  • 2
  • 10
  • I'm not exactly sure how it would solve my problem. I've explained it further in the original post, i wasn't clear enough. Thanks anyways, storing elements somewhere else additionally to the heap didn't cross my mind. That may be useful. – Noname Feb 23 '18 at 17:10
  • No need to store elements somewhere else. Just add a link field and link the elements without copying them. – freim Feb 23 '18 at 18:07