Balances a heap by bubbling up from the given element.
Type | Intent | Optional | Attributes | Name | ||
---|---|---|---|---|---|---|
type(dbcsr_heap_type), | intent(inout) | :: | heap | |||
integer, | intent(in) | :: | first | |||
integer, | intent(out) | :: | new_pos |
SUBROUTINE bubble_up(heap, first, new_pos)
!! Balances a heap by bubbling up from the given element.
TYPE(dbcsr_heap_type), INTENT(INOUT) :: heap
INTEGER, INTENT(IN) :: first
INTEGER, INTENT(OUT) :: new_pos
INTEGER :: e, parent
INTEGER(kind=valt) :: my_value, parent_value
LOGICAL :: all_done
DBCSR_ASSERT(0 < first .AND. first <= heap%n)
e = first
all_done = .FALSE.
IF (e .GT. 1) THEN
my_value = get_value(heap, e)
END IF
! Check whether we are finished, i.e,. whether the element to
! bubble up is an orphan.
new_pos = e
DO WHILE (e .GT. 1 .AND. .NOT. all_done)
! Switches the parent and the current element if the current
! element's value is greater than the parent's value.
parent = get_parent(e)
parent_value = get_value(heap, parent)
IF (my_value .LT. parent_value) THEN
CALL dbcsr_heap_swap(heap, e, parent)
e = parent
ELSE
all_done = .TRUE.
END IF
END DO
new_pos = e
END SUBROUTINE bubble_up