1 files changed, 53 insertions, 0 deletions
diff --git a/src/heap.h b/src/heap.h
new file mode 100644
index 0000000..6ae6507
--- /dev/null
+++ b/src/heap.h
@@ -0,0 +1,53 @@
+/* SPDX-License-Identifier: GPL-3.0-or-later */
+
+#pragma once
+
+#include <stddef.h>
+#include <stdint.h>
+
+//
+// This module implements a binary heap, specifically a min-heap. Each node contains a 64-bit
+// value and a pointer to user data (user data is reused when nodes are extracted). All memory
+// is a single contiguous chunk.
+//
+// In a min-heap, the root node always has the smallest value. The root node can be
+// acquired with heap_next_extract() and extracted (removed) with heap_extract().
+// The runtime of heap_extract() is O(log n).
+//
+// Prior to insertion, the node that will be inserted can already be obtained with
+// heap_next_insert(), which MUST be succeeded by heap_insert() to actually insert the node.
+// The runtime of heap_insert() is O(log n).
+//
+
+typedef struct {
+    uint64_t value;
+    void* user;
+} heap_node_t; //!< Node in a heap
+
+typedef struct {
+    heap_node_t* nodes;
+    size_t capacity;
+    size_t count;
+} heap_t; //!< Min-heap data structure
+
+/// Initialize a min-heap with the given capacity. The user_sizeof parameter specifies the size
+/// of user data stored in each node.
+/// Returns 0 on success, -1 on allocation failure.
+int heap_init(heap_t* heap, size_t capacity, size_t user_sizeof);
+
+/// Obtain the heap node that will be inserted next.
+/// Returns heap node on success, or nullptr if the heap is full.
+heap_node_t* heap_next_insert(heap_t* heap);
+
+/// Insert a value into the heap.
+void heap_insert(heap_t* heap, uint64_t value);
+
+/// Peek the minimum value in the heap without removing it.
+/// Returns heap node on success, or nullptr if the heap is empty.
+heap_node_t* heap_next_extract(heap_t* heap);
+
+/// Extract a node from the heap.
+void heap_extract(heap_t* heap);
+
+/// Free all resources associated with the heap.
+void heap_free(heap_t* heap);