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?

Post by leopardpm »

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:

ADD element
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
            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
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
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Post by paul doe »

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

ADD element
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: 862
Joined: May 05, 2015 5:35
Location: Germany

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

Post by grindstone »

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: 1795
Joined: Feb 28, 2009 20:58

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

Post by leopardpm »

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?

Post by leopardpm »

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
badidea
Posts: 2586
Joined: May 24, 2007 22:10
Location: The Netherlands

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

Post by badidea »

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
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

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

Post by paul doe »

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?

Post by leopardpm »

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?

Post by leopardpm »

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

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

Post by paul doe »

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.
badidea
Posts: 2586
Joined: May 24, 2007 22:10
Location: The Netherlands

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

Post by badidea »

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: 1795
Joined: Feb 28, 2009 20:58

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

Post by leopardpm »

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

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

Post by grindstone »

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?

Post by leopardpm »

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: 862
Joined: May 05, 2015 5:35
Location: Germany

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

Post by grindstone »

Another question: Are there negative values?
Post Reply