pic_heap – PIC

A concrete binary heap keyed by integer(int64) and carrying an integer(int32) payload. This is the data structure behind Dijkstra, A*, k-nearest searches and discrete-event simulation loops.

### Key and payload kinds

The key is a fixed-width integer(int64) and the payload a fixed-width integer(int32). These are deliberate, algorithmic kind choices and must not become default_int: the key must hold accumulated distances or costs without overflowing on a 32-bit default integer build, and the payload is a node index in a CSR-style graph, which is 32-bit by convention. Sizes, capacities and internal indices do use integer(default_int).

### Ordering

Min-heap by default: pop returns the smallest key. Pass max_heap = .true. to init to get a max-heap, where pop returns the largest key. Everything else behaves identically.

### Tie-breaking (guaranteed, not incidental)

Entries with equal keys pop in FIFO order: the entry pushed first pops first. This holds for a max-heap too, and it holds across the rebalancing that push and pop perform. It is implemented by carrying a monotonically increasing insertion counter alongside every entry and comparing (key, insertion index) lexicographically. Since insertion indices are unique, the heap order is a total order and the pop sequence is fully determined by the sequence of pushes. Downstream algorithms are therefore reproducible across runs and compilers.

Entries loaded by build_from are treated as if they had been pushed in array order, so equal keys pop in increasing array-index order.

### Growth

Storage grows geometrically by a factor of 2 (GROWTH_FACTOR), starting at DEFAULT_CAPACITY = 16 slots, so push is amortized O(1). Use reserve to pre-size the heap and avoid reallocation in hot loops. Capacity never shrinks; clear keeps the storage for reuse and destroy releases it.

### Usage

 type(heap_t) :: heap
 type(error_t) :: err
 integer(int64) :: key
 integer(int32) :: payload

 call heap%init(1024_default_int)
 call heap%push(7_int64, 3_int32)
 call heap%push(2_int64, 9_int32)
 do while (.not. heap%is_empty())
    call heap%pop(key, payload, err)
    if (err%has_error()) exit
 end do

Uses

- pic_types
- pic_error
Help

Graph Key

Nodes of different colours represent the following:

Solid arrows point from a submodule to the (sub)module which it is descended from. Dashed arrows point from a module or program unit to modules which it uses.
Where possible, edges connecting nodes are given different colours to make them easier to distinguish in large graphs.

Used by

Help

Graph Key

Nodes of different colours represent the following:

Solid arrows point from a submodule to the (sub)module which it is descended from. Dashed arrows point from a module or program unit to modules which it uses.
Where possible, edges connecting nodes are given different colours to make them easier to distinguish in large graphs.

Variables

Type	Visibility	Attributes		Name		Initial
integer(kind=default_int),	private,	parameter	::	DEFAULT_CAPACITY	=	16	Number of slots allocated by the first growth of an empty heap
integer(kind=default_int),	private,	parameter	::	GROWTH_FACTOR	=	2	Capacity multiplier used when the heap runs out of slots

Derived Types

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
procedure, public :: capacity => heap_capacity
procedure, public :: clear => heap_clear
procedure, public :: destroy => heap_destroy
procedure, public :: init => heap_init
procedure, public :: is_empty => heap_is_empty
procedure, public :: peek => heap_peek
procedure, public :: pop => heap_pop
procedure, public :: push => heap_push
procedure, public :: reserve => heap_reserve
procedure, public :: size => heap_size

Functions

private pure function heap_capacity(self) result(cap)

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

Arguments

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

Return Value integer(kind=default_int)

private pure function heap_is_empty(self) result(empty)

.true. when the heap holds no entries.

Arguments

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

Return Value logical

private pure function heap_size(self) result(n)

Number of entries currently in the heap.

Arguments

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

Return Value integer(kind=default_int)

private pure function precedes(self, left, right) result(first)

.true. when entry left must pop before entry right.

Arguments

Type	Intent		Name
class(heap_t),	intent(in)	::	self
integer(kind=default_int),	intent(in)	::	left
integer(kind=default_int),	intent(in)	::	right

Return Value logical

private function root_entry(self, key, payload, err) result(ok)

Fetch the root entry, reporting an error when the heap is empty.

Arguments

Type	Intent	Optional		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

Return Value logical

Subroutines

private subroutine grow_int32(arr, n_keep, new_cap)

integer(int32) counterpart of grow_int64.

Arguments

Type	Intent	Attributes		Name
integer(kind=int32),	intent(inout),	allocatable	::	arr(:)
integer(kind=default_int),	intent(in)		::	n_keep
integer(kind=default_int),	intent(in)		::	new_cap

private subroutine grow_int64(arr, n_keep, new_cap)

Reallocate arr to new_cap slots, keeping its first n_keep values.

Arguments

Type	Intent	Attributes		Name
integer(kind=int64),	intent(inout),	allocatable	::	arr(:)
integer(kind=default_int),	intent(in)		::	n_keep
integer(kind=default_int),	intent(in)		::	new_cap

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

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

Arguments

Type	Intent	Optional		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

private subroutine heap_clear(self)

Remove every entry but keep the allocated storage for reuse.

Arguments

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

private subroutine heap_destroy(self)

Release the heap storage and reset it to empty.

Arguments

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

private subroutine heap_init(self, cap, max_heap)

Initialise the heap, discarding any previous contents.

Arguments

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

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

Return the root entry without removing it.

Arguments

Type	Intent	Optional		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

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

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

Arguments

Type	Intent	Optional		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

private subroutine heap_push(self, key, payload)

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

Arguments

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

private subroutine heap_reserve(self, n)

Ensure room for at least n entries without further reallocation.

Arguments

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

private pure subroutine sift_down(self, start)

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

Arguments

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

private pure subroutine sift_up(self, start)

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

Arguments

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

private pure subroutine swap_entries(self, left, right)

Exchange two heap slots, key, payload and insertion index together.

Arguments

Type	Intent		Name
class(heap_t),	intent(inout)	::	self
integer(kind=default_int),	intent(in)	::	left
integer(kind=default_int),	intent(in)	::	right

pic_heap Module

Contents

Variables

Derived Types

Functions

Subroutines

Uses

Used by

Variables

Derived Types

type, public :: heap_t

Components

Type-Bound Procedures

Functions

private pure function heap_capacity(self) result(cap)

Arguments

Return Value integer(kind=default_int)

private pure function heap_is_empty(self) result(empty)

Arguments

Return Value logical

private pure function heap_size(self) result(n)

Arguments

Return Value integer(kind=default_int)

private pure function precedes(self, left, right) result(first)

Arguments

Return Value logical

private function root_entry(self, key, payload, err) result(ok)

Arguments

Return Value logical

Subroutines

private subroutine grow_int32(arr, n_keep, new_cap)

Arguments

private subroutine grow_int64(arr, n_keep, new_cap)

Arguments

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

Arguments

private subroutine heap_clear(self)

Arguments

private subroutine heap_destroy(self)

Arguments

private subroutine heap_init(self, cap, max_heap)

Arguments

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

Arguments

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

Arguments

private subroutine heap_push(self, key, payload)

Arguments

private subroutine heap_reserve(self, n)

Arguments

private pure subroutine sift_down(self, start)

Arguments

private pure subroutine sift_up(self, start)

Arguments

private pure subroutine swap_entries(self, left, right)

Arguments