I am implementing a priority queue using a pairing heap. I have a working implementation that supports the following operations.

1. Push O(1).
2. Pop O(lgN).
3. Erase O(lgN).
4. Decrease Key o(lgN).

My priority queue elements are defined as follows:

struct pq_elem
{
    struct pq_elem *left_child;
    struct pq_elem *next_sibling;
    struct pq_elem *prev_sibling;
    struct pq_elem *parent;
};

The structure of the tree is the ring representation suggested by Fredman et al. in their origninal paper on the data structure on page 125, figure 14. I have added in the doubly linked list to support a fast erase and decrease key operation.

Is there a merge and pair technique I can use to ensure that elements with duplicate values that are pushed into the queue are popped in FIFO order? Pseudo code is fine.

If you understand the question, you can stop reading here. If you would like an example of how my priority queue currently pushes and pops elements, and why it does not exhibit round robin fairness among duplicate values, keep reading.

I will push the following elements in the following order (left to right) into the priority queue. The vl is the key and the id is used to illustrate the order elements are pushed and popped.

|id 0| |id 1| |id 2| |id 3| |id 4| |id 5|
|vl 1| |vl 9| |vl 1| |vl 9| |vl 1| |vl 9|

Ideally, here is the order I would get when popping the elements from the priority queue (left to right).

|id 0| |id 2| |id 4| |id 1| |id 3| |id 5|
|vl 1| |vl 1| |vl 1| |vl 9| |vl 9| |vl 9|

In practice, my priority queue does not pop in this order, and here is a full sequence of tree merge and delete min operations that illustrates why. My delete min operation is a one-pass right to left pairing and accumulation operation.

push val = 1

|id:0|
|vl:1|

push val = 9

    |id:0|
    |vl:1|
   /
|id:1|
|vl:9|

push val = 1

     |id:0|
     |vl:1|
    /
|id:2||id:1|
|vl:1||vl:9|

push val = 9

     |id:0|
     |vl:1|
    /
|id:3||id:2||id:1|
|vl:9||vl:1||vl:9|

push val = 1

     |id:0|
     |vl:1|
    /
|id:4||id:3||id:2||id:1|
|vl:1||vl:9||vl:1||vl:9|

push val 9

     |id:0|
     |vl:1|
    /
|id:5||id:4||id:3||id:2||id:1|
|vl:9||vl:1||vl:9||vl:1||vl:9|

pop id = 0

|id:5||id:4|     |id:2||id:1|
|vl:9||vl:1|     |vl:1||vl:9|
                /
            |id:3|
            |vl:9|

         |
         v

|id:5||id:4|     |id:2|
|vl:9||vl:1|     |vl:1|
                /
            |id:1||id:3|
            |vl:9||vl:9|

         |
         v

     |id:4|       |id:2|
     |vl:1|       |vl:1|
    /            /
|id:5|       |id:1||id:3|
|vl:9|       |vl:9||vl:9|

         |
         v

          |id:2|
          |vl:1|
         /
     |id:4||id:1||id:3|
     |vl:1||vl:9||vl:9|
    /
|id:5|
|vl:9|

pop id = 2

     |id:4|      |id:3|
     |vl:1|      |vl:9|
    /
|id:1||id:5|
|vl:9||vl:9|

     |
     v

     |id:4|
     |vl:1|      
    /
|id:3||id:1||id:5|
|vl:9||vl:9||vl:9|

pop id = 4

      |id:1||id:5|
      |vl:9||vl:9|
     /
|id:3|
|vl:9|

     |
     v
           |id:5|
           |vl:9|
          /
      |id:1|
      |vl:9|
     /
|id:3|
|vl:9|

pop id = 5

      |id:1|
      |vl:9|
     /
|id:3|
|vl:9|

pop id = 1

|id:3|
|vl:9|

pop id = 3

The final pop sequence was:

|id 0| |id 2| |id 4| |id 5| |id 1| |id 3|
|vl 1| |vl 1| |vl 1| |vl 9| |vl 9| |vl 9|

The order of elements is preserved during the push phase because the newest value takes the left child position of the parent. But the pairing phase during a delete min operation modifies the order among elements with equivalent values. Any ideas on how to make the delete min operation preserve FIFO order for elements with duplicate values would be appreciated. I can also provide the current code for delete_min and merge if requested but the post is already quite long.