Anyone have good code for making a Priority Queue?

General FreeBASIC programming questions.
leopardpm
Posts: 1792
Joined: Feb 28, 2009 20:58

Anyone have good code for making a Priority Queue?

A priority Queue is basically an array which maintains a sorted order. I made a basic one (below) which just uses a Bubble Sort based insertion sort to ADD elements to the list. This is pretty slow...

The Basic Functions needed for a Priority Queue are:

Access the lowest(highest) element
DEL an element
FIND an element

I am hoping someone has some routines to maintain a priority list with at least a Binary Search function for the 'FIND' and perhaps incorporating some sort of HEAP structure.

I use Priority Queues for pathfinding (A* and Djistras, Flow/Heatmap generating, etc) and now I am thinking of using one for Event Timing in my main game loop...

Here is my basic routines:

Code: Select all

dim shared as integer frontier(1000,2)
' frontier for pathfinding (#, cost=0 x=1 y=2 )????????
dim shared as integer frontpointer

' some subroutines....
declare function FrontierAdd(ByVal frontX as integer, ByVal frontY as integer, ByVal frontCost as integer) as integer
function FrontierAdd(ByVal frontX as integer, ByVal frontY as integer, ByVal frontCost as integer) as integer
' this function uses and alters the shared variables: frontier(9000,2) & frontpointer

' ... add it to the end then bubble sort it down...
dim as integer bub, frontHere
frontpointer = frontpointer + 1
frontHere = frontpointer
frontier(frontpointer,0) = frontCost
frontier(frontpointer,1) = frontX
frontier(frontpointer,2) = frontY
if frontpointer > 1 then
bub = frontpointer
do
if frontier(bub,0) > frontier(bub-1,0) then
swap frontier(bub,0) , frontier(bub-1,0)
swap frontier(bub,1) , frontier(bub-1,1)
swap frontier(bub,2) , frontier(bub-1,2)
frontHere = bub - 1
else
bub = 2 ' early exit
end if
bub = bub - 1
loop until bub < 2
end if
return frontHere
end function

declare function FrontierDel(ByVal thisOne as integer) as integer
function FrontierDel(ByVal thisOne as integer) as integer

select case thisOne
case is < frontpointer
for i as integer = thisOne to (frontpointer-1)
frontier(i,0) = frontier(i+1,0)
frontier(i,1) = frontier(i+1,1)
frontier(i,2) = frontier(i+1,2)
next i
frontpointer = frontpointer - 1
case is = frontpointer
frontpointer = frontpointer - 1
end select
return thisOne
end function

dim as integer newCost, here
here = 0
do
cls
newCost = 0
print "Frontier Pointer = ";frontpointer
print "Last one was at:";here
if frontpointer > 0 then
for i as integer = 1 to frontpointer
print "#";i;" = (";frontier(i,0);")"
next i
end if
print
print "Enter Number to ADD, or negative to DEL that pointer"
input "Number:",newCost
select case newCost
case is > 0
case is < 0
' if negative then newcost is the pointer, not the cost
here = FrontierDel(abs(newCost))
end select

loop until newCost = 0
end

I realize using the 'SWAP' function is a slow way of exchanging variable values... and opening a space for inserting a new member of the list could be done with memcpy or some such fast bulk memory mover....
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Anyone have good code for making a Priority Queue?

leopardpm wrote:...
The Basic Functions needed for a Priority Queue are:

Access the lowest(highest) element
DEL an element
FIND an element

You're confusing a sorted heap with a priority queue. You can't 'find' an item in a priority queue, since the only value that makes sense is the top of the heap. The rest will be unordered and finding something just amounts to a linear search (thus defeating the purpose of the queue). The only operations allowed in a 'pure' priority queue are pushing and popping of values. And you can also of course peek the TOH without popping it (using the top() method here):

Code: Select all

#ifndef __FBFRAMEWORK_COLLECTIONS_PRIORITY_QUEUE__
#define __FBFRAMEWORK_COLLECTIONS_PRIORITY_QUEUE__

namespace FbFramework
'' Some definitions needed
type DisposeCallback _
as sub( byval as any ptr )
const as any ptr Null = 0

namespace Collections
/'
Represents an element of the priority queue

There's no need to instantiate or extend this class, as it is
used by the internal heap only.
'/
type QueueElement
public:
declare constructor( _
byval as integer, _
byval as any ptr, _
byval as DisposeCallback = Null )

declare destructor()

declare property priority() as integer
declare property value() as any ptr

private:
declare constructor()
/'
These are disallowed because we really don't want any
direct duplication of these.
'/
declare constructor( _
byref as QueueElement )
declare operator let( _
byref as QueueElement )

'' The priority of this element
m_priority as integer

'' The value associated with this element
m_value as any ptr

'' The callback function for garbage collection
m_disposeCallback as DisposeCallback
end type

constructor QueueElement( _
byval pPriority as integer, _
byval pValue as any ptr, _
byval pDisposeCallback as DisposeCallback = Null )

m_priority = pPriority
m_value = pValue
m_disposeCallback = pDisposeCallback
end constructor

constructor QueueElement()
end constructor

constructor QueueElement( _
byref rhs as QueueElement )
end constructor

operator QueueElement.let( _
byref rhs as QueueElement )
end operator

destructor QueueElement()
/'
Invoke the callback if it exists for disposal of the 'value'
field if required.
'/
if( _
m_disposeCallback <> Null ) then
m_disposeCallback( m_value )
end if
end destructor

property QueueElement.priority() as integer
return( m_priority )
end property

property QueueElement.value() as any ptr
return( m_value )
end property

/'
This is the base class for the Priority Queue class.

The class represents a Queue data structure, implemented
here as a Binary Heap. Look at these links for more info:
https://en.wikipedia.org/wiki/Priority_queue
https://en.wikipedia.org/wiki/Heap_(data_structure)
https://en.wikipedia.org/wiki/Binary_heap
'/
type Queue
public:
'' Public enumeration to express the priority order we want
enum PriorityOrder
Ascending
Descending
end enum

declare constructor( _
byval as uinteger )
declare constructor( _
byval as PriorityOrder )
declare constructor( _
byval as uinteger, _
byval as PriorityOrder )

declare destructor()

declare property size() as uinteger
declare property count() as uinteger
declare property priority() as PriorityOrder

declare function push( _
byval as integer, _
byval as any ptr, _
byval as DisposeCallback = Null _
) as QueueElement ptr

declare function pop() as any ptr
declare function top() as any ptr

private:
declare constructor()

declare sub initializeComponent()
declare sub resize( _
byval as uinteger )

'' The internal heap
as QueueElement ptr _
m_elements( any )
as uinteger _
_ '' Current size and element count
m_size, m_count, _
_ '' Control the resizing mechanism
m_initialSize, m_lowerBound

'' The selected priority order for this instance
as PriorityOrder m_priorityOrder
end type

constructor Queue( _
byval aPriorityOrder as PriorityOrder )
'' The default size is set to 128 items
this.constructor( _
128, _
aPriorityOrder )
end constructor

constructor Queue( _
byval aSize as uinteger )
/'
Note that the default priority order is set to 'Descending'
since this property is usually understood as 'the higher
the value, the higher the priority'
'/
this.constructor( _
aSize, _
PriorityOrder.Ascending )
end constructor

constructor Queue( _
byval aSize as uinteger, _
byval aPriorityOrder as Queue.PriorityOrder )
/'
Primary constructor

Note that we're using a 1-based array instead of a more common
0-based one. This makes a lot of things easier down the road,
especially adding an element: since we're declaring the   element
count as unsigned, leaving a bit of space at the root of the
heap we don't have to check for underflow conditions during the
sifting.
'/
m_size = _
iif( _
aSize < 1, _
1, _
aSize )
m_priorityOrder = aPriorityOrder

redim _
m_elements( 1 to m_size )

m_count = 0
m_initialSize = m_size
m_lowerBound = 1
end constructor

destructor Queue()
'' Delete all elements if the heap
for _
i as integer = 1 to m_count
delete( m_elements( i ) )
next
end destructor

property Queue.count() as uinteger
return( m_count )
end property

property Queue.size() as uinteger
return( m_size )
end property

property Queue.priority() as PriorityOrder
return( m_priorityOrder )
end property

sub Queue.resize( byval newSize as uinteger )
/'
Resizes the internal array used as the heap.

The algorithm works like this:
When you instantiate the list, the initial size is recorded, and
is used to determine when the list is resized, and by how much. In
this case, the array grows every time the number of items exceed
the initial value by half, and shrinks every time that the previous
size is exceeded also by half.

This way, you'll always have a 'window', centered around the current
item count. Hence, most of the resizing will happen during bulk
addition or deletion operations, not when there's a relatively
balanced number of them.
'/
newSize = _
iif( _
newSize < m_initialSize, _
m_initialSize, _
newSize )

m_size = newSize

m_lowerBound = _
m_size - m_initialSize - ( m_initialSize shr 1 )
m_lowerBound = _
iif( _
m_lowerBound < m_initialSize, _
1, _
m_lowerBound )

redim preserve _
m_elements( 1 to m_size )
end sub

function Queue.push( _
byval pPriority as integer, _
byval pValue as any ptr, _
byval pDisposeCallback as sub( byval as any ptr ) = Null _
) as QueueElement ptr
/'
Enqueues (adds) an element to the tail of the heap

Whenever one adds an element to a binary heap, the heap has to be
rebalanced (a process known as 'sifting') to leave it in a valid
state. The procedure starts at the tail and proceeds towards the root.

Look here for a reference on how this is implemented:
https://en.wikipedia.org/wiki/Heap_(data_structure)#Implementation
'/
'' This will hold the added element
dim as QueueElement ptr newElement

'' Increment the number of elements in the heap
m_count += 1

'' Resize the internal heap if needed
if( _
m_count > m_size - m_initialSize shr 1 ) then
resize( m_size + m_initialSize )
end if

'' Set the current element position to the tail of the heap
dim as uinteger elementPosition = m_count

'' Creates the QueueElement associated with this position
newElement = new QueueElement( _
pPriority, _
pValue )
m_elements( elementPosition ) = newElement

'' The parent position of this element
dim as uinteger parentPosition

'' Controls if the element needs to be swapped with its parent
dim as boolean needSwap

/'
Sift the heap until the enqueued element reaches its correct
position or it bubbles all the way to the root of the heap.

The parent position of the considered element can be computed
as the considered element position \ 2 in a 1-based array.
'/
do
parentPosition = elementPosition shr 1

if( _
parentPosition > 0 ) then
'' Reset the boolean flag
needSwap = false

/'
Depending on the priority order, see if we need to swap the
considered element with its parent.
'/

select case as const m_priorityOrder
case PriorityOrder.Ascending
if( _
m_elements( elementPosition )->priority < _
m_elements( parentPosition )->priority ) then

/'
Swap positions if the considered element's priority is
*lower* than that of its parent
'/
needSwap = true
end if

case PriorityOrder.Descending
if( _
m_elements( elementPosition )->priority > _
m_elements( parentPosition )->priority ) then
/'
Swap positions if the considered element's priority is
*higher* than that of its parent
'/
needSwap = true
end if
end select
/'
Swap the considered element with its parent and update the
element's position to that of its parent to continue the
sifting.
'/
if( _
needSwap ) then
swap _
m_elements( elementPosition ), _
m_elements( parentPosition )
elementPosition = parentPosition
else
'' No need to swap, element is already at the correct position
exit do
end if
else
'' Element is already at the root, end the sifting
exit do
end if
loop

/'
Returns the newly enqueued element

This allows to cache the element for fast lookups if needed. Be
careful how you use this!
'/
return( newElement )
end function

function Queue.pop() as any ptr
/'
Dequeues (removes) an element from the heap

The heap has to be sifted also when removing elements, this time
starting from the head (the root) element and proceeding towards
the tail.
'/

if( _
m_count > 0 ) then
'' Fetch the 'value' at the root of the heap
dim as any ptr elementValue = m_elements( 1 )->value

'' Delete the QueueElement associated with it
delete( m_elements( 1 ) )
m_elements( 1 ) = Null

'' Then, bring the element on the tail of the heap to the root
swap _
m_elements( 1 ), _
m_elements( m_count )

'' Decrement the element count to account for the removed element
m_count -= 1

'' Resize the internal heap if needed
if( _
m_count < m_lowerBound ) then
resize( m_size - m_initialSize )
end if

/'
Here, the element at the root of the heap is successively checked
against its two siblings to swap their positions if necessary. The
current element position is set at the root of the heap to start
the sifting.
'/
dim as uinteger _
elementPosition = 1, _
_ '' The computed positions of both siblings of the considered element
child1Position, child2Position, _
_ '' The potentially new position the element could take
newPosition

'' Flag to determine if we swap the element or not
dim as boolean needSwap
/'
If there's still elements remaining in the heap, we need to reorder them
to account for the removal of it's previous root element. The sifting
direction depends on how the class was instantiated (in 'Ascending' or
'Descending' priority order).
'/

do _
while( m_count > 0 )
'' Compute the positions of the two siblings of the element
child1Position = elementPosition shl 1
child2Position = child1Position + 1

'' Check if the element has one or two siblings
if( _
child1Position <= m_count ) then
if( _
child2Position <= m_count ) then
/'
The element has two siblings, see which of the two we need to swap
according to the desired priority order, and record its position.
'/
select case as const m_priorityOrder
case PriorityOrder.Ascending
'' Set the new potential position to the *lowest* of the two siblings
newPosition = _
iif( _
m_elements( child1Position )->priority < m_elements( child2Position )->priority, _
child1Position, _
child2Position )

case PriorityOrder.Descending
'' Set the new potential position to the *highest* of the two siblings
newPosition = _
iif( _
m_elements( child1Position )->priority > m_elements( child2Position )->priority, _
child1Position, _
child2Position )
end select
else
'' Only one sibling left, always record its position
newPosition = child1Position
end if

'' Reset the flag
needSwap = false

'' Check to see if we need to swap the element with its sibling
select case as const m_priorityOrder
case PriorityOrder.Ascending
needSwap = _
iif( _
m_elements( elementPosition )->priority > m_elements( newPosition )->priority, _
true, _
false )

case PriorityOrder.Descending
needSwap = _
iif( _
m_elements( elementPosition )->priority < m_elements( newPosition )->priority, _
true, _
false )
end select
/'
If needed, swap the considered element's position with the new position computed
above, and set the current element position to the new one to continue the sifting
from there.
'/
if( _
needSwap ) then
swap _
m_elements( elementPosition ), _
m_elements( newPosition )
elementPosition = newPosition
else
'' Element is already in its correct position
exit do
end if
else
'' Element bubbled to the tail of the heap
exit do
end if
loop

'' Return the root element value
return( elementValue )
end if

'' If there's no elements in the heap, return a null pointer
return( Null )
end function

function Queue.top() as any ptr
/'
Peeks the top value field of the root of the heap, without removing it.

If you specified a dispose callback for elements in the heap, be
careful not to delete them manually using this method or you'll crash
the app when the heap is deleted (since it'll invoke a function pointer
on an element that's not there anymore).

It will return a null pointer if the heap is empty.
'/
if( _
m_count > 0 ) then
return( m_elements( 1 )->value )
else
return( Null )
end if
end function
end namespace
end namespace

#endif

/'
Test code
'/
var pq = FbFrameWork.Collections.Queue( _
FbFramework.Collections.Queue.PriorityOrder.Descending )

dim as integer _
numElements = 1000

'' Add some elements to the queue
for _
i as integer = 1 to numElements
dim as integer _
priority = rnd() * numElements

pq.push( _
priority, _
cptr( any ptr, priority ) )
next

'' Retrieve them
for _
i as integer = 0 to pq.count - 1
? pq.pop()
next

sleep()

As you can see, it has nothing to do with maintaining the whole heap sorted, only a few elements are sorted upon insertion and retrieval. The implementation shown here is fully abstract, meaning that it stores a pointer to something (in your case, the cells the pathing algorithm is considering in its 'open' list). Here I just cast the priority to a pointer to store it, for demonstration purposes.

You can also specify a callback in case you need to also dispose of the elements stored upon popping them (not very useful in this case, IMO, but the possibility is there anyway, to maintain orthogonality with other data structures in my framework).
grindstone
Posts: 650
Joined: May 05, 2015 5:35
Location: Germany

Re: Anyone have good code for making a Priority Queue?

IMHO the fastest way to get a sorted list is to implement it as a chained list of UDTs. I've already done something similar, but for strings, not for integers. To give you an idea what I'm talking of, here a quick and dirty 1st approach:

Code: Select all

Type tFrontier
prevNode As Any Ptr
nextNode As Any Ptr
frontCost As Integer
frontX As Integer
frontY As Integer
End Type

Dim As tFrontier Ptr frontier = Callocate(SizeOf(tFrontier))
'frontier->frontCost = 7

Function FrontierAdd(fp As tFrontier Ptr, ByVal frontX As Integer, ByVal frontY As Integer, ByVal frontCost As Integer) As tFrontier Ptr
Dim As tFrontier Ptr oldPrevNode, newNode = Callocate(SizeOf(tFrontier)), fpp = fp, ret = fp

newNode->frontCost = frontCost
newNode->frontX = frontX
newNode->frontY = frontY

Do While fpp
If fpp->frontCost > frontCost Then 'search the first value > frontCost --> insert new node previous
If fpp->prevNode Then 'previous node exists
oldPrevNode = fpp->prevNode 'get pointer for access
newNode->prevNode = oldPrevNode 'previous node of fpp becomes the previous node of newNode
oldPrevNode->nextNode = newNode 'newNode becomes the nextNode of the former previous node
Else
ret = newNode 'new 1st node of the list
EndIf
fpp->prevNode = newNode 'newNode becomes the previous node of fpp
newNode->nextNode = fpp 'fpp becomes nextNode of newNode
Return ret
Else 'next node
If fpp->nextNode Then
fpp = fpp->nextNode
Else 'no value > frontCost found --> append newNode to list
newNode->prevNode = fpp
fpp->nextNode = newNode
Exit Do
EndIf
EndIf
Loop
Return ret

End Function

Sub FrontierTraverse(fp As tFrontier Ptr)
Dim As tFrontier Ptr fpp = fp

Do While fpp
Print fpp->frontCost, fpp->frontX, fpp->frontY,"/";fpp->prevNode,fpp,fpp->nextNode
fpp = fpp->nextNode
Loop
End Sub

Sub FrontierErase(fp As tFrontier Ptr)
Dim As tFrontier Ptr fpp = fp, nextFpp

Do While fpp
nextFpp = fpp->nextNode
DeAllocate fpp
fpp = nextFpp
Loop

End Sub

frontier = FrontierAdd(frontier, 100, 100, 1)
frontier = FrontierAdd(frontier, 200, 200, 10)
frontier = FrontierAdd(frontier, 300, 300, 5)
frontier = FrontierAdd(frontier, 400, 400, 100)
frontier = FrontierAdd(frontier, 400, 400, 7)
frontier = FrontierAdd(frontier, 700, 400, -5)

FrontierTraverse(frontier)

Sleep

FrontierErase(frontier)

'    Dim Shared As Integer frontier(1000,2)
'    ' frontier for pathfinding (#, cost=0 x=1 y=2 )????????
'    Dim Shared As Integer frontpointer
'
'' some subroutines....
'Declare Function FrontierAdd(ByVal frontX As Integer, ByVal frontY As Integer, ByVal frontCost As Integer) As Integer
'Function FrontierAdd(ByVal frontX As Integer, ByVal frontY As Integer, ByVal frontCost As Integer) As Integer
'' this function uses and alters the shared variables: frontier(9000,2) & frontpointer
'
'' ... add it to the end then bubble sort it down...
'    Dim As Integer bub, frontHere
'    frontpointer = frontpointer + 1
'    frontHere = frontpointer
'    frontier(frontpointer,0) = frontCost
'    frontier(frontpointer,1) = frontX
'    frontier(frontpointer,2) = frontY
'    If frontpointer > 1 Then
'        bub = frontpointer
'        Do
'            If frontier(bub,0) > frontier(bub-1,0) Then
'                Swap frontier(bub,0) , frontier(bub-1,0)
'                Swap frontier(bub,1) , frontier(bub-1,1)
'                Swap frontier(bub,2) , frontier(bub-1,2)
'                frontHere = bub - 1
'            Else
'                bub = 2 ' early exit
'            End If
'            bub = bub - 1
'        Loop Until bub < 2
'    End If
'    Return frontHere
'End Function
'
'Declare Function FrontierDel(ByVal thisOne As Integer) As Integer
'Function FrontierDel(ByVal thisOne As Integer) As Integer
'
'    Select Case thisOne
'        Case Is < frontpointer
'            For i As Integer = thisOne To (frontpointer-1)
'                frontier(i,0) = frontier(i+1,0)
'                frontier(i,1) = frontier(i+1,1)
'                frontier(i,2) = frontier(i+1,2)
'            Next i
'            frontpointer = frontpointer - 1
'        Case Is = frontpointer
'            frontpointer = frontpointer - 1
'    End Select
'    Return thisOne
'End Function
'
'Dim As Integer newCost, here
'here = 0
'Do
'    Cls
'    newCost = 0
'    Print "Frontier Pointer = ";frontpointer
'    Print "Last one was at:";here
'    If frontpointer > 0 Then
'        For i As Integer = 1 To frontpointer
'            Print "#";i;" = (";frontier(i,0);")"
'        Next i
'    End If
'    Print
'    Print "Enter Number to ADD, or negative to DEL that pointer"
'    Input "Number:",newCost
'    Select Case newCost
'        Case Is > 0
'            here = FrontierAdd(0,0,newCost)
'        Case Is < 0
'            ' if negative then newcost is the pointer, not the cost
'            here = FrontierDel(Abs(newCost))
'    End Select
'
'Loop Until newCost = 0
'End
leopardpm
Posts: 1792
Joined: Feb 28, 2009 20:58

Re: Anyone have good code for making a Priority Queue?

paul doe wrote:You're confusing a sorted heap with a priority queue.

interesting.... learn something new every day.

So....in a Priority Queue, you can only access one item - the 'top' of the queue... and it will be either the smallest (or largest) value depending on how the Queue is set up, right? So, a Priority Queue is useful for pathfinding (djistras, A*, etc), but maintaining a sorted list/heap might be what I want for a Timer Event List - because there might be a need to find and remove a member within the list, not just accessing the lowest value event each time.
leopardpm
Posts: 1792
Joined: Feb 28, 2009 20:58

Re: Anyone have good code for making a Priority Queue?

grindstone,
in comparing the two methods, your method has the same slow time as mine for finding a particular member, but yours has trivial time to 'insert' a new member at any location. Could yours (I am awful with pointer stuff) be made so that a Binary Search could be used to find a member? I guess it would need a new, sorted list (by referenced value) of the pointers, right?

The functions that I want fast (trivial) are:
accessing/deleting the Least most value (done)
ADDing a new value (search/find location(slow), insert(mine=slow, grindstone=fast))
DELeting a particular value (search/find location(slow), delete(mine=slow,grindstone=fast)

I am assuming a Binary Search function would be fast enough to speed up the ADD/DEL functions to acceptable levels
Posts: 1545
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Anyone have good code for making a Priority Queue?

Would a 'Binary search tree' or 'sorted binary tree' (https://en.wikipedia.org/wiki/Binary_search_tree) fit the requirements?
Edit: Posted this while you just added the 'binary search tree' suggestion yourself.
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Anyone have good code for making a Priority Queue?

leopardpm wrote:So....in a Priority Queue, you can only access one item - the 'top' of the queue... and it will be either the smallest (or largest) value depending on how the Queue is set up, right? So, a Priority Queue is useful for pathfinding (djistras, A*, etc), but maintaining a sorted list/heap might be what I want for a Timer Event List - because there might be a need to find and remove a member within the list, not just accessing the lowest value event each time.

Indeed. Priority queues are used to retrieve the lowest F-cost node from the open list in algorithms such as A* (see here). For the other application, you might want to use another, different data structure as other members suggested here.
leopardpm
Posts: 1792
Joined: Feb 28, 2009 20:58

Re: Anyone have good code for making a Priority Queue?

badidea wrote:Would a 'Binary search tree' or 'sorted binary tree' (https://en.wikipedia.org/wiki/Binary_search_tree) fit the requirements?
Edit: Posted this while you just added the 'binary search tree' suggestion yourself.

in looking at grindstone's method, I think it already is a binary tree structure so my last question to him is redundant - he just hasn't implemented the 'find' function in his example
leopardpm
Posts: 1792
Joined: Feb 28, 2009 20:58

Re: Anyone have good code for making a Priority Queue?

Thanks Paul! I have been using the terms 'Priority Queue' and 'sorted List' interchangeably and it is important to know the difference.
paul doe
Posts: 922
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Anyone have good code for making a Priority Queue?

leopardpm wrote:The functions that I want fast (trivial) are:
accessing/deleting the Least most value (done)
ADDing a new value (search/find location(slow), insert(mine=slow, grindstone=fast))
DELeting a particular value (search/find location(slow), delete(mine=slow,grindstone=fast)

I am assuming a Binary Search function would be fast enough to speed up the ADD/DEL functions to acceptable levels

That depends on the data, mostly. You can use a hash table implementation that indexes into buckets of priority queues, for example. That will address all the speed requirements you need, at the usual tradeoff of speed vs. memory, of course.
Posts: 1545
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Anyone have good code for making a Priority Queue?

I was working on a 'binary tree' in 2016 apparently. It does something, but seems unfinished. Also, there is a maximum number of nodes.

Code: Select all

'Info: https://en.wikipedia.org/wiki/Binary_tree

'Translation of: http://www.cprogramming.com/tutorial/lesson18.html

'=== todo ===
'Change memory allocation
'Walk reverse

type node_type
dim as integer value
dim as node_type ptr pLeft
dim as node_type ptr pRight
end type

type btree_type
public:
declare constructor()
declare destructor()
declare sub initTree(_maxAlloc as integer)
declare sub insert(value as integer)
declare sub walk(pTarget as integer ptr, targetSize as integer)
declare sub killTree()
private:
dim as integer iWalk, maxWalk
dim as integer maxAlloc = 0
dim as integer numAlloc = 0
dim as node_type ptr pNodes
declare sub insert(value as integer, pTree as node_type ptr)
declare sub walk(pTarget as integer ptr, pTree as node_type ptr)
declare function allocPtr() as node_type ptr
end type

'public
constructor btree_type()
maxAlloc = 0
numAlloc = 0
end constructor

'public
destructor btree_type()
killTree()
end destructor

'public
sub btree_type.initTree(_maxAlloc as integer)
maxAlloc = _maxAlloc
pNodes = new node_type[_maxAlloc]
numAlloc = 0
end sub

'public
sub btree_type.insert(value as integer)
if (numAlloc = 0) then
pNodes = allocPtr()
*pNodes = type<node_type>(value, 0, 0)
else
insert(value, pNodes)
end if
end sub

'public
sub btree_type.walk(pTarget as integer ptr, targetSize as integer)
iWalk = 0
maxWalk = targetSize
walk(pTarget, pNodes)
end sub

'public
sub btree_type.killTree()
if (pNodes <> 0) then delete[] pNodes
pNodes = 0
end sub

'private, non-recursive
sub btree_type.insert(value as integer, pTree as node_type ptr)
dim as node_type ptr pTemp = pTree
while (pTemp <> 0)
if (value < pTemp->value) then
if (pTemp->pLeft = 0) then
pTemp->pLeft = allocPtr()
*pTemp->pLeft = type<node_type>(value, 0, 0)
pTemp = 0 'set zero for exit
else
pTemp = pTemp->pLeft
end if
else
if (pTemp->pRight = 0) then
pTemp->pRight = allocPtr()
*pTemp->pRight = type<node_type>(value, 0, 0)
pTemp = 0 'set zero for exit
else
pTemp = pTemp->pRight
end if
end if
wend
end sub

'private, recursive
sub btree_type.walk(pTarget as integer ptr, pTree as node_type ptr)
if (pTree->pRight <> 0) then
walk(pTarget, pTree->pRight)
end if
'check target array size
if (iWalk < maxWalk) then
pTarget[iWalk] = pTree->value
iWalk += 1
else
exit sub
end if
if (pTree->pLeft <> 0) then
walk(pTarget, pTree->pLeft)
end if
end sub

'private
function btree_type.allocPtr() as node_type ptr
dim as node_type ptr pTemp = 0
if (numAlloc < maxAlloc) then
pTemp = pNodes + numAlloc
numAlloc += 1
end if
return pTemp
end function

'============================ test code for btree_type =========================

const as integer N = 10
dim as integer dataRandom(N-1)
dim as integer dataSorted(N-1)
dim as integer i
dim as btree_type bt
dim as double tStart, tEnd
dim as integer loopCount = 0

randomize(timer())

'while(inkey() = "")
bt.initTree(N)
print "=== tree_add ==="
for i = 0 to N-1
dataRandom(i) = int((rnd()-0.5)*20) '-10 ... +10
next

'tStart = timer()
for i = 0 to N-1
bt.insert(dataRandom(i))
next
'tEnd = timer()
'print "tEnd - tStart", tEnd - tStart

for i = 0 to N-1
print str(dataRandom(i)) & " ";
next
print

print "=== tree_walk ==="
'tStart = timer()
bt.walk(@dataSorted(0), N)
'tEnd = timer()
'print "tEnd - tStart", tEnd - tStart

for i = 0 to N-1
print str(dataSorted(i)) & " ";
next
print

print "=== tree_kill ==="
bt.killTree()
loopCount +=1
print "loopCount: "; loopCount
'wend

print "End."
leopardpm
Posts: 1792
Joined: Feb 28, 2009 20:58

Re: Anyone have good code for making a Priority Queue?

This thread is related to a larger goal which I just posted in the Game DEV section:
https://www.freebasic.net/forum/viewtopic.php?f=15&p=255476#p255476
grindstone
Posts: 650
Joined: May 05, 2015 5:35
Location: Germany

Re: Anyone have good code for making a Priority Queue?

Like I said, my posted code is only a 1st approach (quick and dirty). I once implemented a search tree for strings, including a fast search function. Please give me some time to recode.

What do you want to get fast: A certain index or a certain value?
leopardpm
Posts: 1792
Joined: Feb 28, 2009 20:58

Re: Anyone have good code for making a Priority Queue?

grindstone wrote:Like I said, my posted code is only a 1st approach (quick and dirty). I once implemented a search tree for strings, including a fast search function. Please give me some time to recode.

What do you want to get fast: A certain index or a certain value?

value

So, finding, adding, deleting any value , and , accessing the first value (smallest or largest value)
grindstone
Posts: 650
Joined: May 05, 2015 5:35
Location: Germany

Re: Anyone have good code for making a Priority Queue?

Another question: Are there negative values?