Lines Matching refs:heap
10 * struct min_heap - Data structure to hold a min-heap.
11 * @data: Start of array holding the heap elements.
12 * @nr: Number of elements currently in the heap.
24 * @less: Partial order function for this heap.
33 /* Sift the element at pos down the heap. */
35 void min_heapify(struct min_heap *heap, int pos,
39 void *data = heap->data;
42 if (pos * 2 + 1 >= heap->nr)
51 if (pos * 2 + 2 < heap->nr) {
68 void min_heapify_all(struct min_heap *heap,
73 for (i = heap->nr / 2; i >= 0; i--)
74 min_heapify(heap, i, func);
77 /* Remove minimum element from the heap, O(log2(nr)). */
79 void min_heap_pop(struct min_heap *heap,
82 void *data = heap->data;
84 if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap"))
88 heap->nr--;
89 memcpy(data, data + (heap->nr * func->elem_size), func->elem_size);
90 min_heapify(heap, 0, func);
99 void min_heap_pop_push(struct min_heap *heap,
103 memcpy(heap->data, element, func->elem_size);
104 min_heapify(heap, 0, func);
107 /* Push an element on to the heap, O(log2(nr)). */
109 void min_heap_push(struct min_heap *heap, const void *element,
112 void *data = heap->data;
116 if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap"))
120 pos = heap->nr;
122 heap->nr++;