Optimize `_sortNodeUp/Down` methods and `_moveNode` method (11x improvement)

[ericbstie]

Fixes #661. Also fixes #665.

Significantly improves runtime:

More details in #661 🚀 🚀 🚀

Summary by CodeRabbit

• New Features

  • Added documentation for version 2.6, highlighting performance improvements for remove and sorting methods, as well as enhancements to tests and documentation.

• Documentation

  • Updated documentation pages to reference the new repository and commit links.
  • Added a changelog entry for version 2.6 in the documentation sidebar and main page.

• Refactor

  • Improved the performance of internal remove and sorting operations in heap structures by optimizing node repositioning logic and simplifying index calculations.

[coderabbitai[bot]]

"""

Walkthrough

This update primarily refactors internal methods of the Heap and HeapAsync classes to optimize heap operations. The init method's heapify loop now correctly starts from the last parent node, and the sift-up and sift-down operations have been reimplemented to use a "hole" movement approach rather than swapping nodes at every step. Documentation files were regenerated to reflect a new repository source and commit hash, and the changelog was updated to include version 2.6, highlighting performance improvements and documentation enhancements.

Changes

Files	Change Summary
src/Heap.ts, src/HeapAsync.ts	Refactored internal heapify, sift-up, and sift-down logic to use a "hole" movement approach rather than swaps; fixed heapify loop to start from last parent node.
docs/functions/toInt.html, docs/types/AsyncComparator.html, docs/types/AsyncIsEqual.html, docs/types/Comparator.html, docs/types/IsEqual.html	Updated documentation source links to new repository and commit; no changes to signatures or content.
docs/index.html	Updated changelog and sidebar to include version 2.6 with performance and documentation improvements.

Sequence Diagram(s)

sequenceDiagram
    participant User
    participant Heap
    participant InternalArray

    User->>Heap: init(array)
    Heap->>Heap: for i = lastParent down to 0
    Heap->>Heap:   _sortNodeDown(i)
    Heap->>InternalArray:   Move nodes using "hole" approach (no swaps)
    Heap-->>User: Heap initialized

    User->>Heap: insert(value)
    Heap->>Heap: _sortNodeUp(index)
    Heap->>InternalArray:   Move nodes using "hole" approach (no swaps)
    Heap-->>User: Value inserted

Assessment against linked issues

Objective	Addressed	Explanation
Optimize sift-up/sift-down to avoid swapping at every iteration, use "hole" movement (ref #661)	✅
Reduce unnecessary function calls in heap operations (ref #661)	✅
Fix init to only run _sortNodeDown on non-leaf nodes (start at last parent node) (ref #665)	✅

Poem

Oh, what a leap for our heap!
No more swapping in a loop so deep,
Now we move a clever hole,
Making performance our new goal.
Docs refreshed, a changelog treat—
This bunny’s code is fast and neat! 🐇✨
"""

---

📜 Recent review details

Configuration used: CodeRabbit UI Review profile: CHILL Plan: Pro

📥 Commits

Reviewing files that changed from the base of the PR and between 0789d20674246ebb808e6e09db577e4701ec24ea and 877e37f885de5887cd790b9866a0d70b8b2a889c.

⛔ Files ignored due to path filters (2)

• dist/heap-js.es5.js is excluded by !**/dist/**
• dist/heap-js.umd.js is excluded by !**/dist/**

📒 Files selected for processing (7)

• docs/functions/toInt.html (1 hunks)
• docs/index.html (2 hunks)
• docs/types/AsyncComparator.html (1 hunks)
• docs/types/AsyncIsEqual.html (1 hunks)
• docs/types/Comparator.html (1 hunks)
• docs/types/IsEqual.html (1 hunks)
• src/Heap.ts (5 hunks)

✅ Files skipped from review due to trivial changes (1)

• docs/index.html

🚧 Files skipped from review as they are similar to previous changes (6)

• docs/functions/toInt.html
• docs/types/AsyncIsEqual.html
• docs/types/IsEqual.html
• docs/types/AsyncComparator.html
• docs/types/Comparator.html
• src/Heap.ts

✨ Finishing Touches

• [ ] 📝 Generate Docstrings

---

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

• X
• Mastodon
• Reddit
• LinkedIn

🪧 Tips

Chat

There are 3 ways to chat with CodeRabbit:

• Review comments: Directly reply to a review comment made by CodeRabbit. Example:
  • I pushed a fix in commit <commit_id>, please review it.
  • Generate unit testing code for this file.
  • Open a follow-up GitHub issue for this discussion.
• Files and specific lines of code (under the "Files changed" tab): Tag @coderabbitai in a new review comment at the desired location with your query. Examples:
  • @coderabbitai generate unit testing code for this file.
  • @coderabbitai modularize this function.
• PR comments: Tag @coderabbitai in a new PR comment to ask questions about the PR branch. For the best results, please provide a very specific query, as very limited context is provided in this mode. Examples:
  • @coderabbitai gather interesting stats about this repository and render them as a table. Additionally, render a pie chart showing the language distribution in the codebase.
  • @coderabbitai read src/utils.ts and generate unit testing code.
  • @coderabbitai read the files in the src/scheduler package and generate a class diagram using mermaid and a README in the markdown format.
  • @coderabbitai help me debug CodeRabbit configuration file.

Note: Be mindful of the bot's finite context window. It's strongly recommended to break down tasks such as reading entire modules into smaller chunks. For a focused discussion, use review comments to chat about specific files and their changes, instead of using the PR comments.

CodeRabbit Commands (Invoked using PR comments)

• @coderabbitai pause to pause the reviews on a PR.
• @coderabbitai resume to resume the paused reviews.
• @coderabbitai review to trigger an incremental review. This is useful when automatic reviews are disabled for the repository.
• @coderabbitai full review to do a full review from scratch and review all the files again.
• @coderabbitai summary to regenerate the summary of the PR.
• @coderabbitai generate docstrings to generate docstrings for this PR.
• @coderabbitai generate sequence diagram to generate a sequence diagram of the changes in this PR.
• @coderabbitai resolve resolve all the CodeRabbit review comments.
• @coderabbitai configuration to show the current CodeRabbit configuration for the repository.
• @coderabbitai help to get help.

Other keywords and placeholders

• Add @coderabbitai ignore anywhere in the PR description to prevent this PR from being reviewed.
• Add @coderabbitai summary to generate the high-level summary at a specific location in the PR description.
• Add @coderabbitai anywhere in the PR title to generate the title automatically.

CodeRabbit Configuration File (.coderabbit.yaml)

• You can programmatically configure CodeRabbit by adding a .coderabbit.yaml file to the root of your repository.
• Please see the configuration documentation for more information.
• If your editor has YAML language server enabled, you can add the path at the top of this file to enable auto-completion and validation: # yaml-language-server: $schema=https://coderabbit.ai/integrations/schema.v2.json

Documentation and Community

• Visit our Documentation for detailed information on how to use CodeRabbit.
• Join our Discord Community to get help, request features, and share feedback.
• Follow us on X/Twitter for updates and announcements.

[ericbstie]

@coderabbitai review

[coderabbitai[bot]]

✅ Actions performed

Review triggered.

Note: CodeRabbit is an incremental review system and does not re-review already reviewed commits. This command is applicable only when automatic reviews are paused.

[ericbstie]

The _moveNode method is now obsolete (not used anywhere), but it might be good to keep it for a while in case some users of the library for some reason use that method 🤷🏻‍♂️

3 improvements to the sortNodeUp/Down were made incrementally in this PR:

1. Use temp variable instead of destructure syntax (this one is later superseded by improvement 3)
2. Use bitshift to calculate parentIndex instead of Math.floor
3. Move only one node during the sortingUp/Down, then insert the value at the correct place at the end (move hole instead of swapping nodes)

Comparison without baseline:

Other

The implementation of the improvements above relied on #665 (start sortNodeDown at length/2, not length in init ) being fixed for the tests to pass.

Script used for visualizations above:

import { lineplot, bench, compact, run } from "mitata";


import { Heap as BaselineHeap } from "heap-js";
import { Heap as MoveNodeImprovedHeap } from "./heap-temp.umd"
import { Heap as BitshiftParentIndexHeap } from "./heap-bitshift.umd"
import { Heap as HoleHeap } from "./heap-hole.umd"


compact(() => {
    lineplot(() => {
        bench("Optimize _moveNode method (no destructure syntax)", function*(ctx: any) {
            yield () => {
                const heap = new MoveNodeImprovedHeap();
                for (let i = ctx.get("size") - 1; i >= 0; i--) { heap.push(i) }
                for (let i = ctx.get("size") - 1; i >= 0; i--) { heap.pop() }
            }
        }).dense_range("size", 100, 50_000, 1_000)
        bench("Use bitshift for parent index", function*(ctx: any) {
            yield () => {
                const heap = new BitshiftParentIndexHeap();
                for (let i = ctx.get("size") - 1; i >= 0; i--) { heap.push(i) }
                for (let i = ctx.get("size") - 1; i >= 0; i--) { heap.pop() }
            }
        }).dense_range("size", 100, 50_000, 1_000)
        bench("Move hole instead of swapping nodes", function*(ctx: any) {
            yield () => {
                const heap = new HoleHeap();
                for (let i = ctx.get("size") - 1; i >= 0; i--) { heap.push(i) }
                for (let i = ctx.get("size") - 1; i >= 0; i--) { heap.pop() }
            }
        }).dense_range("size", 100, 50_000, 1_000)
    })
})

await run();

[CarlOlson]

@ignlg Is this able to be merged? The tests pass locally (not sure why CI failed, but the log expired).

If this merges, then this library will be competitive with the fastest implementations. And due to the clean code, good testing, and full API, it would be the preferred implementation by a large margin!

[ignlg]

This PR must point to next branch to create a pre-release first. I will do it as soon as possible and push this forward.