sledge-serverless-framework icon indicating copy to clipboard operation
sledge-serverless-framework copied to clipboard

Published 20 hours ago • verified publisher icon gwsystems

Sledge heap removal takes O(n)

Open emil916 opened this issue 3 years ago • 0 comments

Currently in Sledge the MinHeap implementation with Priority Queue has the delete API implemented with O(n) time complexity.

https://github.com/gwsystems/sledge-serverless-framework/blob/9778db645aeac6fa98979707e2afa54db72929e8/runtime/include/priority_queue.h#L369-L386

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

emil916 avatar Jul 27 '21 12:07 emil916