using System;

using System.Collections.Generic;

public class Program

{

    // https://www.codechick.io/tutorials/dsa/dsa-heap

    public static void Main()

    {

        var queue = new PrioritisedQueue();

        Console.WriteLine("====== Queue one by one ======");

        queue.Queue(1);

        queue.Queue(2);

        queue.Queue(9);

        queue.Queue(7);

        queue.Queue(5);

        queue.Queue(3);

        Console.WriteLine("Print:");

        queue.Print();

        Console.WriteLine("Dequeue:");

        while(queue.Count > 0)

        {

            Console.WriteLine("\t" + queue.Dequeue());

        }

        Console.WriteLine("====== Queue range ======");

        queue.QueueRange(new int[] { 1,2,9,7,5,3 });

        Console.WriteLine("Print:");

        queue.Print();

        Console.WriteLine("Dequeue:");

        while(queue.Count > 0)

        {

            Console.WriteLine("\t" + queue.Dequeue());      

        }

    }

}

​

public class PrioritisedQueue

{

    private List<int> values = new List<int>();

    public int Count => values.Count;

    public void QueueRange(int[] input)

    {

        values.AddRange(input);

        for (int i = values.Count / 2 - 1; i >= 0; i--)

            MakeHeap(i);

    }

    public void Queue(int value)

    {

        if (values.Count == 0)

        {

            values.Add(value);  

        }

        else

        {

            values.Add(value);

            for (int i = values.Count / 2 - 1; i >= 0; i--)

            {

                MakeHeap(i);

            }

        }

    }

    public int Dequeue()

    {

        if (values.Count == 0) return -1;

        var size = values.Count;

        var last = values.Count - 1;

        var temp = values[0];

        values[0] = values[last];

        values[last] = temp;

        values.RemoveAt(last);

        for (int i = size / 2 - 1; i >= 0; i--)

            MakeHeap(i);

        return temp;

    }

    public void Print()

    {

        Console.WriteLine(string.Join(", ", values));

    }

    private void MakeHeap(int i)

    {

        var size = values.Count;

        var left = 2 * i + 1;

        var right = 2 * i + 2;

        var largest = i;

        if (left < size && values[left] > values[largest])

            largest = left;

        if (right < size && values[right] > values[largest])

            largest = right;

        if (largest != i)

        {

            var temp = values[i];

            values[i] = values[largest];

            values[largest] = temp;

            MakeHeap(largest);

        }

    }

}