Skip to content

Binary heap implemenation has O(n) complexity instead of O(log n) #249

Description

@alefbragin

https://github.com/solidstate-network/solidstate-solidity/blob/d1ba52d0981e3d1e1feda525dca8dd0c07ea4a00/contracts/data/BinaryHeap.sol#L251C1-L259C6

Heapify procedure is used in every add/remove operations. Heapify has while loop that call another heapify function exactly len/2. It's O(n).

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No 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