Heaps and Priority Queues - osvaldoandrade/ova-lib GitHub Wiki

Heaps and Priority Queues

Read this page when the top element is the only element you need immediately and that top element is defined by a comparator instead of by insertion order.

Heap Constructor and Shared API

The heap constructor is:

heap *create_heap(HeapType type, int capacity, comparator compare_function);

Every heap exposes:

Field	Meaning
`put(self, item)`	inserts one item
`put_with_handle(self, item)`	inserts and returns a handle when supported
`decrease_key(self, node_handle, new_value)`	updates priority when supported
`delete_node(self, node_handle)`	removes one node by handle when supported
`pop(self)`	removes and returns the top item or `NULL`
`peek(self)`	returns the current top item or `NULL`
`size(self)`	returns the current count
`free(self)`	frees heap storage

The Comparator Rule Is Not the Same in Both Heap Types

The current source uses 2 comparator directions.

The binary heap treats cmp(a, b) > 0 as “a outranks b.”

The Fibonacci heap treats cmp(a, b) < 0 as “a outranks b.”

That difference matters if you move the same comparator between both heap types. The shipped tests show the intended usage:

For BINARY_HEAP, an integer comparator that returns positive for larger integers produces max-heap behavior.

For FIBONACCI_HEAP, the tests invert the integer comparator to get the same max-heap behavior.

`BINARY_HEAP`

BINARY_HEAP is array-backed and takes the capacity hint seriously.

Use it when you need priority order, peek, pop, and growth, but do not need a handle back from insertion.

Supported operations:

Operation	Support
`put`	yes
`pop`	yes
`peek`	yes
`size`	yes
`put_with_handle`	no
`decrease_key`	no
`delete_node`	no

When the internal array fills, capacity doubles until the safe-capacity helper reaches its limit.

`FIBONACCI_HEAP`

FIBONACCI_HEAP is pointer-based and ignores the capacity hint.

Use it when your algorithm needs a stable handle for an inserted node and later needs to raise that node’s priority or delete it by handle.

Supported operations:

Operation	Support
`put`	yes
`put_with_handle`	yes
`decrease_key`	yes
`delete_node`	yes
`pop`	yes
`peek`	yes
`size`	yes

The handle returned by put_with_handle is an internal node pointer. Treat it as opaque. It becomes invalid after delete_node, after the node is removed from the heap, or after free.

decrease_key follows algorithm-textbook naming, but the public effect is “increase the node’s priority according to this heap’s comparator rule.”

Priority Queue Wrapper

create_queue(QUEUE_TYPE_PRIORITY, capacity, cmp) is a queue API over the binary heap.

That wrapper never exposes handles and never switches to the Fibonacci heap. If you need decrease_key or delete_node, stay on the heap API.

Empty-Case Behavior

pop and peek return NULL on an empty heap.

Ownership and Cleanup

Heaps store payload pointers. They do not copy payloads and do not free payloads.

Destroy the heap with heap->free(heap). Free user payloads in your own code when your program owns them.