Documentation/core-api/min_heap.rst

4 Min Heap API
12 The Min Heap API provides a set of functions and macros for managing min-heaps
13 in the Linux kernel. A min-heap is a binary tree structure where the value of
17 This document provides a guide to the Min Heap API, detailing how to define and
36 Min-Heap Definition
39 The core data structure for representing a min-heap is defined using the
41 you to define a min-heap with a preallocated buffer or dynamically allocated
50         size_t nr;         /* Number of elements in the heap */
52         _type *data;    /* Pointer to the heap data */
58 A typical heap structure will include a counter for the number of elements
59 (`nr`), the maximum capacity of the heap (`size`), and a pointer to an array of
61 heap storage using **MIN_HEAP_PREALLOCATED**.
63 Min Heap Callbacks
67 elements in the heap and swapping them. It contains two function pointers:
77 - **swp** is a function for swapping elements in the heap. If swp is set to
83 The following macro wrappers are provided for interacting with the heap in a
85 heap, and they abstract away direct calls to internal functions.
89 Heap Initialization
94     min_heap_init(heap, data, size);
96 - **heap**: A pointer to the min-heap structure to be initialized.
97 - **data**: A pointer to the buffer where the heap elements will be stored. If
98   `NULL`, the preallocated buffer within the heap structure will be used.
99 - **size**: The maximum number of elements the heap can hold.
101 This macro initializes the heap, setting its initial state. If `data` is
102 `NULL`, the preallocated memory inside the heap structure will be used for
105 **Inline Version:** min_heap_init_inline(heap, data, size)
112     element = min_heap_peek(heap);
114 - **heap**: A pointer to the min-heap from which to retrieve the smallest
117 This macro returns a pointer to the smallest element (the root) of the heap, or
118 `NULL` if the heap is empty. The operation is **O(1)**.
120 **Inline Version:** min_heap_peek_inline(heap)
122 Heap Insertion
127     success = min_heap_push(heap, element, callbacks, args);
129 - **heap**: A pointer to the min-heap into which the element should be inserted.
130 - **element**: A pointer to the element to be inserted into the heap.
135 This macro inserts an element into the heap. It returns `true` if the insertion
136 was successful and `false` if the heap is full. The operation is **O(log n)**.
138 **Inline Version:** min_heap_push_inline(heap, element, callbacks, args)
140 Heap Removal
145     success = min_heap_pop(heap, callbacks, args);
147 - **heap**: A pointer to the min-heap from which to remove the smallest element.
152 This macro removes the smallest element (the root) from the heap. It returns
153 `true` if the element was successfully removed, or `false` if the heap is
156 **Inline Version:** min_heap_pop_inline(heap, callbacks, args)
158 Heap Maintenance
161 You can use the following macros to maintain the heap's structure:
165     min_heap_sift_down(heap, pos, callbacks, args);
167 - **heap**: A pointer to the min-heap.
173 This macro restores the heap property by moving the element at the specified
174 index (`pos`) down the heap until it is in the correct position. The operation
177 **Inline Version:** min_heap_sift_down_inline(heap, pos, callbacks, args)
181     min_heap_sift_up(heap, idx, callbacks, args);
183 - **heap**: A pointer to the min-heap.
189 This macro restores the heap property by moving the element at the specified
190 index (`idx`) up the heap. The operation is **O(log n)**.
192 **Inline Version:** min_heap_sift_up_inline(heap, idx, callbacks, args)
196     min_heapify_all(heap, callbacks, args);
198 - **heap**: A pointer to the min-heap.
203 This macro ensures that the entire heap satisfies the heap property. It is
204 called when the heap is built from scratch or after many modifications. The
207 **Inline Version:** min_heapify_all_inline(heap, callbacks, args)
214     success = min_heap_del(heap, idx, callbacks, args);
216 - **heap**: A pointer to the min-heap.
222 This macro removes an element at the specified index (`idx`) from the heap and
223 restores the heap property. The operation is **O(log n)**.
225 **Inline Version:** min_heap_del_inline(heap, idx, callbacks, args)
230 - **min_heap_full(heap)**: Checks whether the heap is full.
235     bool full = min_heap_full(heap);
237 - `heap`: A pointer to the min-heap to check.
239 This macro returns `true` if the heap is full, otherwise `false`.
241 **Inline Version:** min_heap_full_inline(heap)
243 - **min_heap_empty(heap)**: Checks whether the heap is empty.
248     bool empty = min_heap_empty(heap);
250 - `heap`: A pointer to the min-heap to check.
252 This macro returns `true` if the heap is empty, otherwise `false`.
254 **Inline Version:** min_heap_empty_inline(heap)
259 An example usage of the min-heap API would involve defining a heap structure,
271         .less = my_less_function,    /* Comparison function for heap order */
278         /* Declare a min-heap */
281         /* Initialize the heap with preallocated buffer and size */
284         /* Build the heap using min_heapify_all */
285         my_heap.nr = 5;  /* Set the number of elements in the heap */