Add real-time versions?
Nobody has claimed this yet.
- Dominant language
- Haskell
- Stars
- 17
- Forks
- 12
- PR merge metrics
- No merged PRs in 30d
Description
I'm really not sure it's worth the trouble, but we could improve the amortized times to worst-case using scheduling. Okasaki's scheme uses a separate schedule, which doesn't seem terribly compact, and his analysis is rather tricky. I think we can do something a bit simpler. The debit invariant allows one debit on the child of a `Skip` node, and no debits anywhere else. We can arrange to force a node as soon as its parent changes from a `Skip` to a `Cons`. To accomplish that, we can arrange to always have access to the first `Skip` node by linking them together.
```haskell
data Scheduled rk a = forall xxrk x. Scheduled !(BinomForest rk a) (BinomForest xxrk x)
data BinomForest rk a
= Nil
-- The second field points to the next Skip node, or Nil if there is none.
| forall xxrk x. Skip (BinomForest (Succ rk) a) (BinomForest xxrk x)
| Cons {-# UNPACK #-} !(BinomTree rk a) !(BinomForest (Succ rk) a)
```
This gives a somewhat segmented flavor. Another option, of course, might be to use a segmented number system. Doing that with nested types will require type-aligned (nonempty) lists; I'm not sure how complicated it will get. And then there are also skew binomial heaps, which I don't really understand yet.
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.
Research direction
Start by comparing the proposed Scheduled and BinomForest definitions with the current priority-queue implementation. Evaluate the linked Skip-node scheduling approach against segmented number systems and skew binomial heaps, then establish whether a real-time implementation can provide worst-case bounds without excessive complexity.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- data
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100