Currently in Sledge the MinHeap implementation with Priority Queue has the delete API implemented with O(n) time complexity.
|
priority_queue_delete_nolock(struct priority_queue *self, void *value) |
|
{ |
|
assert(self != NULL); |
|
assert(value != NULL); |
|
assert(!listener_thread_is_running()); |
|
assert(!self->use_lock || LOCK_IS_LOCKED(&self->lock)); |
|
|
|
for (int i = 1; i <= self->size; i++) { |
|
if (self->items[i] == value) { |
|
self->items[i] = self->items[self->size]; |
|
self->items[self->size--] = NULL; |
|
priority_queue_percolate_down(self, i); |
|
return 0; |
|
} |
|
} |
|
|
|
return -1; |
|
} |
It can be reduced to O(logn) by keeping the new array elements' indices as within the struct properties and update it on every change. Sample from the composite codebase:
https://github.com/gwsystems/composite/blob/fa9e07f6790bfb73fe8d043538a8e95b87ad5f90/src/components/lib/util/heap.c#L238
Particularly the index update function u() is helpful:
https://github.com/gwsystems/composite/blob/loader/src/components/lib/util/heap.c#L289-L293
Currently in Sledge the MinHeap implementation with Priority Queue has the
deleteAPI implemented with O(n) time complexity.sledge-serverless-framework/runtime/include/priority_queue.h
Lines 369 to 386 in 9778db6
It can be reduced to O(logn) by keeping the new array elements' indices as within the struct properties and update it on every change. Sample from the composite codebase:
https://github.com/gwsystems/composite/blob/fa9e07f6790bfb73fe8d043538a8e95b87ad5f90/src/components/lib/util/heap.c#L238
Particularly the index update function
u()is helpful:https://github.com/gwsystems/composite/blob/loader/src/components/lib/util/heap.c#L289-L293