Stable Priority Queue feature not working as expected

[UbhiTS]

One of the features states : Has a stable priority queue implementation (ie. if two items are enqueued with the same priority, they'll be dequeued in the same order they were enqueued)

However, the below code fails this feature test, please can you fix. Thanks

class Program
{
    private const int MAX_QUEUE_LENGTH = 10000;

    static void Main(string[] args)
    {
        FastPriorityQueue<GeocodingRequest> priorityQueue = new FastPriorityQueue<GeocodingRequest>(MAX_QUEUE_LENGTH);

        // HIGH PRIORITY REQUESTS
        var highReq1 = new GeocodingRequest("HIGH 1", 1, "{ }");
        var highReq2 = new GeocodingRequest("HIGH 2", 2, "{ }");
        var highReq3 = new GeocodingRequest("HIGH 3", 1, "{ }");
        var highReq4 = new GeocodingRequest("HIGH 4", 2, "{ }");

        // LOW PRIORITY REQUESTS
        var lowReq1 = new GeocodingRequest("LOW 1", 1, "{ }");
        var lowReq2 = new GeocodingRequest("LOW 2", 2, "{ }");
        var lowReq3 = new GeocodingRequest("LOW 3", 1, "{ }");
        var lowReq4 = new GeocodingRequest("LOW 4", 2, "{ }");

        // ENQUEUE REQUESTS
        priorityQueue.Enqueue(lowReq1, (int)Priority.Low);
        priorityQueue.Enqueue(lowReq2, (int)Priority.Low);
        priorityQueue.Enqueue(highReq1, (int)Priority.High);
        priorityQueue.Enqueue(highReq2, (int)Priority.High);
        priorityQueue.Enqueue(highReq3, (int)Priority.High);
        priorityQueue.Enqueue(highReq4, (int)Priority.High);
        priorityQueue.Enqueue(lowReq3, (int)Priority.Low);
        priorityQueue.Enqueue(lowReq4, (int)Priority.Low);

        while (priorityQueue.Count != 0)
        {
            var nextGeocodingRequest = priorityQueue.Dequeue();
            Console.WriteLine(nextGeocodingRequest.Tag);
        }

        // OUTPUT is actually as below       But should be as below
        // HIGH 4                            HIGH 1
        // HIGH 2                            HIGH 2
        // HIGH 1                            HIGH 3
        // HIGH 3                            HIGH 4
        // LOW 1                             LOW 1
        // LOW 4                             LOW 2
        // LOW 2                             LOW 3
        // LOW 3                             LOW 4

        Console.ReadLine();
    }
}

public class GeocodingRequest : FastPriorityQueueNode
{
    public string Tag { get; set; }
    public int Batch { get; set; }
    public string Payload { get; set; }
    public GeocodingRequest(string tag, int batch, string payload)
    {
        Tag = tag;
        Batch = batch;
        Payload = payload;
    }
}

public enum Priority
{
    Unknown = 0,
    High = 1,
    Medium = 2,
    Low = 3,
}

[BlueRaja]

The stable implementation is called StablePriorityQueue. It's mentioned in the documentation. I plan on making it even more clear in the next iteration.