Removing any value from the heap

[flekschas]

This is more of a suggestion / question for an enhancement than a bug or issue.

In short: expand poll and peek to values at indices other than 0.

In long: I am using the queue to keep track of properties on a set of elements. In my case, the set of elements can be split into two at some point, in which case I am creating a new set and update the old set (i.e., remove elements now being part of the new set). I would like to avoid having to re-heapify the elements on the old set so I expanded the poll function to accept an integer such that any value on the heap can be removed. Same addition for the peek.

The changes are minimal:

FastPriorityQueue.prototype.peek = function (i) {
    i = i | 0;
    if (this.size == 0 || i >= this.size) return undefined;
    return this.array[i];
};

FastPriorityQueue.prototype.poll = function (i) {
    i = i | 0;
    if (this.size == 0 || i >= this.size) return undefined;
    var ans = this.array[i];
    if (this.size > 1) {
        this.array[i] = this.array[--this.size];
        this._percolateDown(i);
    } else {
        this.size -= 1;
    }
    return ans;
};

(peek(i) is not expected to return the i-th element in terms of the priority but merely the i-th element on the array.)

I am wondering if this addition could be useful in general, hence, worth a pull request or if you want to keep things simple?

I've set up a fork and added a unit test in case you are interested: https://github.com/flekschas/FastPriorityQueue.js

[lemire]

Pull requests are always welcome.

Comments:

1. I am uneasy about overloading poll/peek with functions that are vastly different in functionality. It seems like it would be best to use different names. To avoid confusion.

2. I am not sure I understand the use case. It would be interesting to verify whether there isn't a better solution to achieve the same functionality. Without a concrete example, it is kind of difficult to do.

[blaskovicz]

@flekschas try out the remove if you see still interested

[lemire]

I am going to close this issue. Please re-open if the fix by @blaskovicz is not satisfactory.