Heap API

Data Structures
struct	JUNO_DS_HEAP_POINTER_API_TAG
	Element-level operations required by the heap. More...
struct	JUNO_DS_HEAP_API_TAG
	Heap API vtable. More...

Functions
struct JUNO_DS_HEAP_ROOT_TAG	JUNO_MODULE_ROOT (JUNO_DS_HEAP_API_T, const JUNO_DS_HEAP_POINTER_API_T *ptHeapPointerApi;JUNO_DS_ARRAY_ROOT_T *ptHeapArray;size_t zLength;)
	Heap root instance and state.
JUNO_STATUS_T	JunoDs_Heap_Insert (JUNO_DS_HEAP_ROOT_T *ptHeap, JUNO_POINTER_T tValue)
	Insert a new element into the heap.
JUNO_STATUS_T	JunoDs_Heap_Heapify (JUNO_DS_HEAP_ROOT_T *ptHeap)
	Transform the underlying array into a heap.
JUNO_STATUS_T	JunoDs_Heap_Pop (JUNO_DS_HEAP_ROOT_T *ptHeap, JUNO_POINTER_T tReturn)
	Pop the root element into tReturn.
JUNO_STATUS_T	JunoDs_Heap_Init (JUNO_DS_HEAP_ROOT_T *ptHeap, const JUNO_DS_HEAP_POINTER_API_T *ptHeapPointerApi, JUNO_DS_ARRAY_ROOT_T *ptHeapArray, JUNO_FAILURE_HANDLER_T pfcnFailureHdlr, JUNO_USER_DATA_T *pvUserData)
	Initialize a heap over a backing array and element pointer API.
JUNO_STATUS_T	JunoDs_Heap_SiftDown (JUNO_DS_HEAP_ROOT_T *ptHeap, size_t iStart)
	Sift down from a starting index to restore the heap property.
static JUNO_STATUS_T	JunoDs_Heap_Verify (JUNO_DS_HEAP_ROOT_T *ptHeap)
	Verify heap configuration and dependent APIs.

Detailed Description

A binary heap interface parameterized by element-level comparison and swap callbacks over an underlying Array. The heap stores elements in a contiguous array (JUNO_DS_ARRAY_ROOT_T) and maintains either a max-heap or min-heap property depending on the user-provided Compare function.

Characteristics

• Deterministic operations with no dynamic allocation; capacity is defined by the backing array.
• Time complexity: Insert O(log n), Pop O(log n), Update O(log n), SiftDown O(log n), Heapify O(n).
• Non-thread-safe by default; protect externally as needed.

Invariants (enforced by implementation and Verify):

• 0 <= zLength <= ptHeapArray->zCapacity
• All required function pointers are non-NULL (heap API, pointer API, array API)
• Backing array verifies via JunoDs_ArrayVerify.

Ordering semantics:

• The user provides Compare(parent, child) that returns true when the heap property holds for that pair. Example: max-heap uses parent >= child; min-heap uses parent <= child. Swap exchanges two elements in storage.

Element ownership:

• Elements are copied into/out of the heap using the JUNO_POINTER_T API (Copy/Reset). Callers must provide valid pointer descriptors describing storage location, size, and alignment.

Function Documentation

JUNO_MODULE_ROOT()

struct JUNO_DS_HEAP_ROOT_TAG JUNO_MODULE_ROOT	(	JUNO_DS_HEAP_API_T	,
		const JUNO_DS_HEAP_POINTER_API_T *ptHeapPointerApi;JUNO_DS_ARRAY_ROOT_T *ptHeapArray;size_t zLength;
	)

Heap root instance and state.

JunoDs_Heap_Heapify()

JUNO_STATUS_T JunoDs_Heap_Heapify

(

JUNO_DS_HEAP_ROOT_T *

ptHeap

)

Transform the underlying array into a heap.

Parameters

ptHeap

Heap instance with zLength set to the count of initialized elements.

Returns

JUNO_STATUS_SUCCESS on success; JUNO_STATUS_ERR when zLength == 0; or propagation of errors from SiftDown.

Note

Complexity O(n).

Transform the underlying array into a heap.

Set zLength to the number of initialized elements, then call Heapify.

Returns

JUNO_STATUS_SUCCESS on success; JUNO_STATUS_ERR when zLength == 0 or if SiftDown reports an error.

JunoDs_Heap_Init()

JUNO_STATUS_T JunoDs_Heap_Init	(	JUNO_DS_HEAP_ROOT_T *	ptHeap,
		const JUNO_DS_HEAP_POINTER_API_T *	ptHeapPointerApi,
		JUNO_DS_ARRAY_ROOT_T *	ptHeapArray,
		JUNO_FAILURE_HANDLER_T	pfcnFailureHdlr,
		JUNO_USER_DATA_T *	pvUserData
	)

Initialize a heap over a backing array and element pointer API.

Parameters

ptHeap	Heap instance to initialize (output).
ptHeapPointerApi	Element-level callbacks (Compare/Swap) defining ordering.
ptHeapArray	Backing array providing capacity and element storage ops.
pfcnFailureHdlr	Optional failure handler for assertions in this module (can be NULL).
pvUserData	Optional user data passed to the failure handler (can be NULL).

Returns

Result of JunoDs_Heap_Verify on the configured heap (SUCCESS on valid configuration, otherwise an error code such as JUNO_STATUS_NULLPTR_ERROR or array verification failures).

JunoDs_Heap_Insert()

JUNO_STATUS_T JunoDs_Heap_Insert	(	JUNO_DS_HEAP_ROOT_T *	ptHeap,
		JUNO_POINTER_T	tValue
	)

Insert a new element into the heap.

Parameters

ptHeap	Heap instance.
tValue	Pointer descriptor for the element to copy into the heap.

Returns

JUNO_STATUS_SUCCESS on success; JUNO_STATUS_ERR if full; or pointer/array errors from SetAt/Compare/Swap/Update.

Note

Complexity O(log n). Capacity is bounded by ptHeapArray->zCapacity.

Insert a new element into the heap.

After a successful insert, you must write the element to the returned index in your storage, then call JunoDs_Heap_Update(...) to bubble it up.

Returns

A result where:

• tStatus = SUCCESS and tOk = new index when there is capacity.
• tStatus = ERR when zLength >= zCapacity (no more space).

JunoDs_Heap_Pop()

JUNO_STATUS_T JunoDs_Heap_Pop	(	JUNO_DS_HEAP_ROOT_T *	ptHeap,
		JUNO_POINTER_T	tReturn
	)

Pop the root element into tReturn.

Parameters

ptHeap	Heap instance.
tReturn	Pointer descriptor receiving a copy of the popped root value.

Returns

JUNO_STATUS_SUCCESS on success; JUNO_STATUS_ERR if the heap is empty; or propagation of errors from Swap/Copy/RemoveAt/SiftDown.

Note

Complexity O(log n).

Pop the root element into tReturn.

Algorithm:

• Swap the root and the last element.
• Call Reset on the last index.
• Decrement zLength and SiftDown from the root.

Error propagation:

• If Reset returns an error, the delete operation returns that error (it is not ignored).

Returns

JUNO_STATUS_SUCCESS on success; JUNO_STATUS_ERR if zLength == 0 or if Swap/Reset/SiftDown report an error.

JunoDs_Heap_SiftDown()

JUNO_STATUS_T JunoDs_Heap_SiftDown	(	JUNO_DS_HEAP_ROOT_T *	ptHeap,
		size_t	iStart
	)

Sift down from a starting index to restore the heap property.

Typical usage:

• Used internally by Pop and Heapify. You can also call it directly if you overwrite the root or another node and need to restore ordering.

Returns:

• JUNO_STATUS_SUCCESS on success.
• JUNO_STATUS_ERR if zLength == 0, if child indices exceed capacity, or if Compare/Swap report an error.

Sift the element at iStart downward until the heap property holds.

Parameters

ptHeap	Heap instance.
iStart	Start index for sifting (commonly 0 after a pop).

Returns

JUNO_STATUS_SUCCESS on success; JUNO_STATUS_ERR if zLength == 0; or propagation of errors from Compare/Swap.

Note

Complexity O(log n).

JunoDs_Heap_Verify()

static JUNO_STATUS_T JunoDs_Heap_Verify ( JUNO_DS_HEAP_ROOT_T *  ptHeap )

inlinestatic

Verify heap configuration and dependent APIs.

Ensures the heap instance and all required API pointers are set, then delegates to JunoDs_ArrayVerify for the backing array. Used by all heap operations to guard preconditions.

Returns

JUNO_STATUS_SUCCESS on valid configuration; an error (e.g., NULLPTR, INVALID_TYPE) otherwise.