Balances a heap by bubbling down from the given element.
Type | Intent | Optional | Attributes | Name | ||
---|---|---|---|---|---|---|
type(dbcsr_heap_type), | intent(inout) | :: | heap | |||
integer, | intent(in) | :: | first |
SUBROUTINE bubble_down(heap, first)
!! Balances a heap by bubbling down from the given element.
TYPE(dbcsr_heap_type), INTENT(INOUT) :: heap
INTEGER, INTENT(IN) :: first
INTEGER :: e, left_child, right_child, smallest
INTEGER(kind=valt) :: left_child_value, min_value, &
right_child_value
LOGICAL :: all_done
!
DBCSR_ASSERT(0 < first .AND. first <= heap%n)
e = first
all_done = .FALSE.
! Check whether we are finished, i.e,. whether the element to
! bubble down is childless.
DO WHILE (e .LE. get_parent(heap%n) .AND. .NOT. all_done)
! Determines which node (current, left, or right child) has the
! smallest value.
smallest = e
min_value = get_value(heap, e)
left_child = get_left_child(e)
IF (left_child .LE. heap%n) THEN
left_child_value = get_value(heap, left_child)
IF (left_child_value .LT. min_value) THEN
min_value = left_child_value
smallest = left_child
END IF
END IF
right_child = left_child + 1
IF (right_child .LE. heap%n) THEN
right_child_value = get_value(heap, right_child)
IF (right_child_value .LT. min_value) THEN
min_value = right_child_value
smallest = right_child
END IF
END IF
!
CALL dbcsr_heap_swap(heap, e, smallest)
IF (smallest .EQ. e) THEN
all_done = .TRUE.
ELSE
e = smallest
END IF
END DO
END SUBROUTINE bubble_down