gwsystems / gwsystems/sledge-serverless-framework
Sledge heap removal takes O(n)
@emil916 is already working on this.
Since Jul 27, 2021.
- Dominant language
- C
- Stars
- 124
- Forks
- 19
- PR merge metrics
- No merged PRs in 30d
Description
Currently in Sledge the MinHeap implementation with Priority Queue has the delete API implemented with O(n) time complexity.
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
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Assessment
This issue has not been assessed yet.