We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Currently in Sledge the MinHeap implementation with Priority Queue has the delete API implemented with O(n) time complexity.
delete
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
u()
The text was updated successfully, but these errors were encountered:
emil916
No branches or pull requests
Currently in Sledge the MinHeap implementation with Priority Queue has the
delete
API 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
The text was updated successfully, but these errors were encountered: