sift_down Subroutine

private pure subroutine sift_down(self, start)

Move entry start towards the leaves until the heap property holds.

Arguments

Type IntentOptional Attributes Name
class(heap_t), intent(inout) :: self
integer(kind=default_int), intent(in) :: start

Calls

proc~~sift_down~~CallsGraph proc~sift_down sift_down proc~precedes precedes proc~sift_down->proc~precedes proc~swap_entries swap_entries proc~sift_down->proc~swap_entries

Called by

proc~~sift_down~~CalledByGraph proc~sift_down sift_down proc~heap_build_from heap_t%heap_build_from proc~heap_build_from->proc~sift_down proc~heap_pop heap_t%heap_pop proc~heap_pop->proc~sift_down proc~a_star a_star proc~a_star->proc~heap_pop proc~dijkstra dijkstra proc~dijkstra->proc~heap_pop

Variables

Type Visibility Attributes Name Initial
integer(kind=default_int), private :: best
integer(kind=default_int), private :: child
integer(kind=default_int), private :: parent

Source Code

   pure subroutine sift_down(self, start)
      !! Move entry `start` towards the leaves until the heap property holds.
      class(heap_t), intent(inout) :: self
      integer(default_int), intent(in) :: start

      integer(default_int) :: parent, child, best

      parent = start
      do
         child = 2*parent
         if (child > self%n_entries) exit

         best = child
         if (child < self%n_entries) then
            if (precedes(self, child + 1, best)) best = child + 1
         end if

         if (.not. precedes(self, best, parent)) exit
         call swap_entries(self, parent, best)
         parent = best
      end do
   end subroutine sift_down