heap_t Derived Type

type, public :: heap_t

Binary heap of (integer(int64) key, integer(int32) payload) pairs with stable FIFO tie-breaking on equal keys.


Components

Type Visibility Attributes Name Initial
integer(kind=int64), private, allocatable :: insertion(:)

Insertion index of each entry, used to break key ties FIFO
integer(kind=int64), private, allocatable :: keys(:)

Heap-ordered keys, valid in 1:n_entries
logical, private :: max_heap = .false.

.true. selects max-heap ordering, .false. min-heap
integer(kind=default_int), private :: n_entries = 0

Number of entries currently stored
integer(kind=int64), private :: n_pushed = 0

Monotonic counter handing out insertion indices
integer(kind=int32), private, allocatable :: payloads(:)

Payload travelling with keys, same index

Type-Bound Procedures

procedure, public :: build_from => heap_build_from

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

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

    Read more…

    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

procedure, public :: capacity => heap_capacity

  • private pure function heap_capacity(self) result(cap)

    Number of entries the heap can hold before it has to grow.

    Arguments

    Type IntentOptional Attributes Name
    class(heap_t), intent(in) :: self

    Return Value integer(kind=default_int)

procedure, public :: clear => heap_clear

  • private subroutine heap_clear(self)

    Remove every entry but keep the allocated storage for reuse.

    Read more…

    Arguments

    Type IntentOptional Attributes Name
    class(heap_t), intent(inout) :: self

procedure, public :: destroy => heap_destroy

  • private subroutine heap_destroy(self)

    Release the heap storage and reset it to empty.

    Arguments

    Type IntentOptional Attributes Name
    class(heap_t), intent(inout) :: self

procedure, public :: init => heap_init

  • private subroutine heap_init(self, cap, max_heap)

    Initialise the heap, discarding any previous contents.

    Read more…

    Arguments

    Type IntentOptional Attributes Name
    class(heap_t), intent(inout) :: self
    integer(kind=default_int), intent(in), optional :: cap
    logical, intent(in), optional :: max_heap

procedure, public :: is_empty => heap_is_empty

  • private pure function heap_is_empty(self) result(empty)

    .true. when the heap holds no entries.

    Arguments

    Type IntentOptional Attributes Name
    class(heap_t), intent(in) :: self

    Return Value logical

procedure, public :: peek => heap_peek

  • private subroutine heap_peek(self, key, payload, err)

    Return the root entry without removing it.

    Read more…

    Arguments

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

procedure, public :: pop => heap_pop

  • private subroutine heap_pop(self, key, payload, err)

    Remove and return the root entry (minimum, or maximum for a max-heap).

    Read more…

    Arguments

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

procedure, public :: push => heap_push

  • private subroutine heap_push(self, key, payload)

    Insert one (key, payload) entry in O(log n).

    Read more…

    Arguments

    Type IntentOptional Attributes Name
    class(heap_t), intent(inout) :: self
    integer(kind=int64), intent(in) :: key
    integer(kind=int32), intent(in) :: payload

procedure, public :: reserve => heap_reserve

  • private subroutine heap_reserve(self, n)

    Ensure room for at least n entries without further reallocation.

    Read more…

    Arguments

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

procedure, public :: size => heap_size

  • private pure function heap_size(self) result(n)

    Number of entries currently in the heap.

    Arguments

    Type IntentOptional Attributes Name
    class(heap_t), intent(in) :: self

    Return Value integer(kind=default_int)

Source Code

   type :: heap_t
      !! Binary heap of (`integer(int64)` key, `integer(int32)` payload) pairs
      !! with stable FIFO tie-breaking on equal keys.
      integer(int64), allocatable, private :: keys(:)
         !! Heap-ordered keys, valid in `1:n_entries`
      integer(int32), allocatable, private :: payloads(:)
         !! Payload travelling with `keys`, same index
      integer(int64), allocatable, private :: insertion(:)
         !! Insertion index of each entry, used to break key ties FIFO
      integer(default_int), private :: n_entries = 0
         !! Number of entries currently stored
      integer(int64), private :: n_pushed = 0
         !! Monotonic counter handing out insertion indices
      logical, private :: max_heap = .false.
         !! `.true.` selects max-heap ordering, `.false.` min-heap
   contains
      procedure :: init => heap_init
      procedure :: clear => heap_clear
      procedure :: destroy => heap_destroy
      procedure :: size => heap_size
      procedure :: is_empty => heap_is_empty
      procedure :: capacity => heap_capacity
      procedure :: reserve => heap_reserve
      procedure :: push => heap_push
      procedure :: pop => heap_pop
      procedure :: peek => heap_peek
      procedure :: build_from => heap_build_from
   end type heap_t