heap_build_from Subroutine

private subroutine heap_build_from(self, keys, payloads, err)

Replace the heap contents with keys/payloads, heapified in O(n).

This is Floyd’s bottom-up heapify, not size(keys) repeated pushes. The two arrays must have the same length, otherwise err reports ERROR_VALIDATION and the heap is left untouched. Equal keys pop in increasing array-index order, matching what pushing the arrays in order would have produced.

Type Bound

heap_t

Arguments

Type IntentOptional Attributes Name
class(heap_t), intent(inout) :: self
integer(kind=int64), intent(in) :: keys(:)
integer(kind=int32), intent(in) :: payloads(:)
type(error_t), intent(out), optional :: err

Calls

proc~~heap_build_from~~CallsGraph proc~heap_build_from heap_t%heap_build_from proc~error_set error_t%error_set proc~heap_build_from->proc~error_set proc~heap_reserve heap_t%heap_reserve proc~heap_build_from->proc~heap_reserve proc~sift_down sift_down proc~heap_build_from->proc~sift_down proc~grow_int32 grow_int32 proc~heap_reserve->proc~grow_int32 proc~grow_int64 grow_int64 proc~heap_reserve->proc~grow_int64 proc~heap_capacity heap_t%heap_capacity proc~heap_reserve->proc~heap_capacity proc~precedes precedes proc~sift_down->proc~precedes proc~swap_entries swap_entries proc~sift_down->proc~swap_entries

Variables

Type Visibility Attributes Name Initial
integer(kind=default_int), private :: i
integer(kind=default_int), private :: n

Source Code

   subroutine heap_build_from(self, keys, payloads, err)
      !! Replace the heap contents with `keys`/`payloads`, heapified in O(n).
      !!
      !! This is Floyd's bottom-up heapify, not `size(keys)` repeated pushes.
      !! The two arrays must have the same length, otherwise `err` reports
      !! `ERROR_VALIDATION` and the heap is left untouched. Equal keys pop in
      !! increasing array-index order, matching what pushing the arrays in
      !! order would have produced.
      class(heap_t), intent(inout) :: self
      integer(int64), intent(in) :: keys(:)
      integer(int32), intent(in) :: payloads(:)
      type(error_t), intent(out), optional :: err

      integer(default_int) :: n, i

      n = int(size(keys), default_int)
      if (int(size(payloads), default_int) /= n) then
         if (present(err)) then
            call err%set(ERROR_VALIDATION, "pic_heap: build_from requires keys and payloads of equal length")
         end if
         return
      end if

      call self%reserve(n)

      do i = 1, n
         self%keys(i) = keys(i)
         self%payloads(i) = payloads(i)
         self%insertion(i) = int(i, int64)
      end do

      self%n_entries = n
      self%n_pushed = int(n, int64)

      do i = n/2, 1, -1
         call sift_down(self, i)
      end do
   end subroutine heap_build_from