How to resolve the algorithm Priority queue step by step in the uBasic/4tH programming language
How to resolve the algorithm Priority queue step by step in the uBasic/4tH programming language
Table of Contents
Problem Statement
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.
Create a priority queue. The queue must support at least two operations:
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:
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.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Priority queue step by step in the uBasic/4tH programming language
Source code in the ubasic/4th programming language
b = -1 ' b points to last entry on the queue
q = FUNC(_Grab) ' now grab the top value
' and display it
Print Peek(q, 0) - Ord("0"), Show(Chop(q, 1))
Print
Proc _Insert(3, "Clear drains") ' insert the whole bunch
Proc _Insert(4, "Feed cat")
Proc _Insert(5, "Make tea")
Proc _Insert(1, "Solve RC tasks")
Proc _Insert(2, "Tax return")
For x = 0 To b: Proc _List(x) : Next ' list all entries
q = FUNC(_Grab) ' now grab the top value
Print ' and display it
Print Peek(q, 0) - Ord("0"), Show(Chop(q, 1))
Print
For x = 0 To b: Proc _List(x) : Next ' list all entries
End
_Grab ' return and remove top entry
Local (2)
' return dummy on error
If b < 0 Then Return ("0No such entry")
a@ = @(0)) ' save the top entry
For b@ = 0 To Set(b, b - 1) : @(b@) = @(b@+1): Next
Return (a@)
_List ' list any (valid) position on queue
Param (1)
If (a@ > b) = 0 Then Print Peek(@(a@), 0) - Ord("0"), Show(Chop(@(a@), 1))
Return
_Insert ' insert an entry
Param (2) ' priority, task
Local (1)
c@ = FUNC(_binarySearch(a@, 0, b)) ' search the position
Proc _MakeRoom (c@) ' make room
@(c@) = Join(Str(a@), b@) ' assign the entry
Return
_binarySearch ' perform a binary search
Param(3) ' value, start index, end index
Local(1) ' The middle of the array
' Ok, signal we didn't find it
If c@ < b@ Then Return (b@) ' first entry on start
d@ = SHL(b@ + c@, -1) ' prevent overflow (LOL!)
If a@ < Peek(@(d@), 0) - Ord("0") Then Return (FUNC(_binarySearch (a@, b@, d@-1)))
If a@ > Peek(@(d@), 0) - Ord("0") Then Return (FUNC(_binarySearch (a@, d@+1, c@)))
If a@ = Peek(@(d@), 0) - Ord("0") Then Return (d@)
Return (-1) ' -1 on error
_MakeRoom ' make some space
Param (1) ' starting position
Local (1)
' from bottom to top
For b@ = Set(b, b+1) To a@ + 1 Step -1: @(b@) = @(b@-1) : Next
Return
You may also check:How to resolve the algorithm Jewels and stones step by step in the Ada programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the MiniScript programming language
You may also check:How to resolve the algorithm Terminal control/Inverse video step by step in the TPP programming language
You may also check:How to resolve the algorithm Boyer-Moore string search step by step in the Julia programming language
You may also check:How to resolve the algorithm Loops/N plus one half step by step in the Befunge programming language