lspitzner / lspitzner/pqueue

Add real-time versions?

Open
#38 6 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.