boostorg / boostorg/heap

Priority queue documentation has wrong complexities

Open
#3 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
20
Forks
44
PR merge metrics
No merged PRs in 30d

Description

The complexity of a pairing heap is stated incorrectly. Amortised and actual complexity of push() should be $O(1)$. Amortised complexity of erase() and pop() should be $log(n)$.

The implementation of the decrease() part of update() would normally be $2**(2sqrt(log(log(n)))$. I don't think the current implementation provides that as the check for empty children list is not conditional on the direction of cost change. As such, update() seems to be unconditionally $log(n)$ amortised, just like an increase() would be. Merge should be $O(1)$ as usual.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.