A priority queue is somewhat similar to a queue, with an important distinction: each item is added to a priority queue with a priority level, and will be later removed from the queue with the highest priority element first. That is, the items are (conceptually) stored in the queue in priority order instead of in insertion order.



Task

Create a priority queue.   The queue must support at least two operations:

   Insertion.   An element is added to the queue with a priority (a numeric value).
   Top item removal.   Deletes the element or one of the elements with the current top priority and return it.


Optionally, other operations may be defined, such as peeking (find what current top priority/top element is), merging (combining two priority queues into one), etc.



To test your implementation, insert a number of elements into the queue, each with some random priority.

Then dequeue them sequentially; now the elements should be sorted by priority.

You can use the following task/priority items as input data:

        Priority         Task
       ══════════   ════════════════
           3         Clear drains
           4         Feed cat
           5         Make tea
           1         Solve RC tasks
           2         Tax return



The implementation should try to be efficient.   A typical implementation has   O(log n)   insertion and extraction time,   where   n   is the number of items in the queue.

You may choose to impose certain limits such as small range of allowed priority levels, limited capacity, etc.   If so, discuss the reasons behind it.




Type Tupla
    Prioridad As Integer
    Tarea As String
End Type
Dim Shared As Tupla a()
Dim Shared As Integer n 'número de eltos. en la matriz, el último elto. es n-1
 
Function Izda(i As Integer) As Integer
    Izda = 2 * i + 1
End Function
 
Function Dcha(i As Integer) As Integer
    Dcha = 2 * i + 2
End Function
 
Function Parent(i As Integer) As Integer
    Parent = (i - 1) \ 2
End Function
 
Sub Intercambio(i As Integer, j As Integer)
    Dim t As Tupla
    t = a(i)
    a(i) = a(j)
    a(j) = t
End Sub
 
Sub bubbleUp(i As Integer)
    Dim As Integer p = Parent(i)
    Do While i > 0 And a(i).Prioridad < a(p).Prioridad
        Intercambio i, p
        i = p
        p = Parent(i)
    Loop
End Sub
 
Sub Annadir(fPrioridad As Integer, fTarea As String)
    n += 1
    If n > Ubound(a) Then Redim Preserve a(2 * n)
    a(n - 1).Prioridad = fPrioridad
    a(n - 1).Tarea = fTarea
    bubbleUp (n - 1)
End Sub
 
Sub trickleDown(i As Integer)
    Dim As Integer j, l, r
    Do
        j = -1
        r = Dcha(i)
        If r < n And a(r).Prioridad < a(i).Prioridad Then
            l = Izda(i)
            If a(l).Prioridad < a(r).Prioridad Then
                j = l
            Else
                j = r
            End If
        Else
            l = Izda(i)
            If l < n And a(l).Prioridad < a(i).Prioridad Then j = l
        End If
        If j >= 0 Then Intercambio i, j
        i = j
    Loop While i >= 0
End Sub
 
Function Remove() As Tupla
    Dim As Tupla x = a(0)
    a(0) = a(n - 1)
    n = n - 1
    trickleDown 0
    If 3 * n < Ubound(a) Then Redim Preserve a(Ubound(a) \ 2)
    Remove = x
End Function
 
 
Redim a(4)
Annadir (3, "Clear drains")
Annadir (4, "Feed cat")
Annadir (5, "Make tea")
Annadir (1, "Solve RC tasks")
Annadir (2, "Tax return")
Dim t As Tupla
Do While n > 0
    t = Remove
    Print t.Prioridad; "  "; t.Tarea
Loop
Sleep