## Anyone have good code for making a Priority Queue?

General FreeBASIC programming questions.
leopardpm
Posts: 1795
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 integerfunction 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 frontHereend functiondeclare function FrontierDel(ByVal thisOne as integer) as integerfunction 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 thisOneend functiondim as integer newCost, herehere = 0do    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 = 0end`

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: 1346
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 namespaceend namespace#endif/'  Test code'/var pq = FbFrameWork.Collections.Queue( _  FbFramework.Collections.Queue.PriorityOrder.Descending )dim as integer _  numElements = 1000'' Add some elements to the queuefor _  i as integer = 1 to numElements  dim as integer _    priority = rnd() * numElements    pq.push( _    priority, _    cptr( any ptr, priority ) )next'' Retrieve themfor _  i as integer = 0 to pq.count - 1  ? pq.pop()nextsleep()`

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: 767
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 IntegerEnd TypeDim As tFrontier Ptr frontier = Callocate(SizeOf(tFrontier))'frontier->frontCost = 7Function 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 FunctionSub 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   LoopEnd SubSub FrontierErase(fp As tFrontier Ptr)   Dim As tFrontier Ptr fpp = fp, nextFpp      Do While fpp      nextFpp = fpp->nextNode      DeAllocate fpp      fpp = nextFpp   Loop   End Subfrontier = 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)SleepFrontierErase(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: 1795
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: 1795
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: 2178
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: 1346
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: 1795
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: 1795
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: 1346
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: 2178
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 reversetype node_type   dim as integer value   dim as node_type ptr pLeft   dim as node_type ptr pRightend typetype 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 ptrend type'publicconstructor btree_type()   maxAlloc = 0   numAlloc = 0end constructor'publicdestructor btree_type()   killTree()end destructor'publicsub btree_type.initTree(_maxAlloc as integer)   maxAlloc = _maxAlloc   pNodes = new node_type[_maxAlloc]   numAlloc = 0end sub'publicsub btree_type.insert(value as integer)   if (numAlloc = 0) then      pNodes = allocPtr()      *pNodes = type<node_type>(value, 0, 0)   else      insert(value, pNodes)   end ifend sub'publicsub btree_type.walk(pTarget as integer ptr, targetSize as integer)   iWalk = 0   maxWalk = targetSize   walk(pTarget, pNodes)end sub'publicsub btree_type.killTree()   if (pNodes <> 0) then delete[] pNodes   pNodes = 0end sub'private, non-recursivesub 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   wendend sub'private, recursivesub 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 ifend sub'privatefunction 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 pTempend function'============================ test code for btree_type =========================const as integer N = 10dim as integer dataRandom(N-1)dim as integer dataSorted(N-1)dim as integer idim as btree_type btdim as double tStart, tEnddim as integer loopCount = 0randomize(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 'wendprint "End."`
leopardpm
Posts: 1795
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: 767
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: 1795
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: 767
Joined: May 05, 2015 5:35
Location: Germany

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

Another question: Are there negative values?