Skip to content

Sledge heap removal takes O(n) #263

@emil916

Description

@emil916

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

Metadata

Metadata

Assignees

Labels

Type

No type
No fields configured for issues without a type.

Projects

No projects

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions