ignlg/heap-js

Efficient Binary heap (priority queue, binary tree) data structure for JavaScript / TypeScript. Includes JavaScript methods, Python's heapq module methods, and Java's PriorityQueue methods.

Hi there 👋

GitHub Stats

Repositories

heap-js's Issues

Dependabot couldn't find the branch next

Dependabot was set up to create pull requests against the branch next, but couldn't find it.

If the branch has been permanently deleted you can update Dependabot's target branch from your dashboard.

View the update logs.

Merge Dependabot PRs

If the Dependabot PRs could be auto merged, that would be great!

https://github.com/marketplace/actions/dependabot-auto-merge

Awesome implementation of Heap!

When the priorities are equal, shouldn't the FIFO principle be followed, but it's not

const Heap = require('heap-js').default

const comparator = (a, b) => {
    if (a.ttl > b.ttl) {
        return 1
    }
    if (a.ttl < b.ttl) {
        return -1
    }
    return 0
}

const equalSamples = [{ id: 1, ttl: 0 }, { id: 2, ttl: 0 }, { id: 3, ttl: 0 }, { id: 4, ttl: 0 }]
it('FIFO when equal compare', () => {
    const heap = new Heap(comparator)
    heap.push(...equalSamples)
    expect([heap.pop(), heap.pop(), heap.pop(), heap.pop()]).toEqual(equalSamples)
})

failed

Consider a sequence that is constantly push() and pop(). If FIFO is not followed, some tasks will never be pop() as long as the sequence is constantly push().

Fix and enhance CI

error [email protected]: The engine "node" is incompatible with this module. Expected version ">=6 <7 || >=8".

I think Node 7 can be removed and how about adding Node 10?

Documentation link on npmjs is broken

The docs link on npmjs gives 404.

Wrong Filename of the Type Definition File

heap-js/package.json

Line 17 in f7d63c5

"types": "dist/types/heap-js.d.ts",

should be

"types": "dist/types/Heap.d.ts", 

Documentation for `limit`

The documentation for limit is sparse, and I for some reason thought it would enforce the heap to keep the top N values. Instead, I'm not actually quite sure what it's doing, or what some practical purposes are for it? Some clarity here would be great, as sometimes my test results with limit returned "correctly" (but it was purely by chance).

Update dependencies

Dependencies should be updated.

Handling asynchronous comparator

Is there a way to handle asynchronous custom priority comparator? If not, is such a feature planned for the near future?

remove(o) should be O(lgn) but is implemented as O(n)

There should be an internal map from item reference to item's index, remove the item, then heapify.
Current implementation searches through the entire heap array for the element.

simplify default compare functions

you can use (a, b) => a-b, (a, b) => b-a for the default minComparator and maxComparator function respectively.
Should be a bit faster than the if -> else if -> else

Issue popping when using custom comparator

Hi,

Thanks for the library! I've had great use of it in a lot of online coding interviews. :)

Here's a quick reproduction of a bug I found when using custom comparators:

const heap = new Heap((a, b) => a[1] - b[1]);
heap.push([1, 2]);
heap.push([6, 0]);
heap.push([2, 3]);
heap.pop();
// => TypeError: Cannot read property '1' of undefined

After some digging, I found that inside getPotentialParent sometimes calls this.compare with an undefined value. Adding a quick typeof this.heapArray[j] !== "undefined" && to the function solves the issue but I am not sure if this is the best way to handle it. I'd be happy to send a PR with tests if you think this is a good solution to the problem.

Documentation page shows 404 for Heap class documentation

Generated documentation generates a wrong link to Heap class documentation.

Current behavior

Heap menu item references /classes/Heap.html.

Expected behavior

Heap menu item must reference the generated file.

Proposed solution

Two options:

• Heap menu item must reference /classes/heap.html.
• Generated file must be renamed to /classes/Heap.html.

Iterator should not modify the heap (it should use nlargest(length) instead of pop)

Currently, this library implements the heap with the pop() method, which causes the heap to be emptied on a single iteration. For example:

import { Heap } from 'heap-js'

const heap = new Heap()
heap.push(10)
heap.push(5)
heap.push(15)
heap.push(3)

// prints 3, 5, 10, 15
for (const item of heap) {
  console.log(item)
}

// does not print anything
for (const item of heap) {
  console.log(item)
}

As it is not a standard behaviour of iterators to modify the underlying data structure, the sorted(nlargest(length)) method should be used instead of pop().