4
\$\begingroup\$

I'm currently going over Robert Sedgewick's Algorithms book. For the implementation of A priority queue using a binary heap I implemented the code using ES6. I believe to have more experience with Ruby but I have come to enjoy working with ES-6 using classes.

I would like feedback on how can the code be improved, if there is anything that can be optimized, if am following best practices or if I'm breaking any principles.

 class Heap {
      constructor() {
        this.n = 0;
        this.pq = [];
      }
    
      size() {
        return this.n;
      }
    
      isEmpty() {
        this.n === 0;
      }
    
      swim(k) {
        while(k > 1 && this.less(Math.floor(k / 2), k)){
          this.exch(Math.floor(k / 2), k);
          k = Math.floor(k / 2)
        }
      }
    
      sink(k) {
        while(2 * k <= this.n) {
          let j = 2 * k;
    
          if(this.pq[j + 1] != null) {
            if(k > 1 && this.less(j, j + 1)){
              j++;
            }
          }
    
          if(this.pq[k] > this.pq[j]) {
            break;
          }
          this.exch(k, j)
          k = j
        }
      }
    
      insert(v) {
        this.pq[++this.n] = v;
        this.swim(this.n);
      }
    
      delMax() {
        let max = this.pq[1];
        this.exch(1, this.n--);
        this.pq[this.n + 1] = null;
        this.sink(1);
        return max;
      }
    
      less(i, j) {
        return this.pq[i] < this.pq[j];
      }
    
      exch(i, j) {
        let temp = this.pq[i];
        this.pq[i] = this.pq[j];
        this.pq[j] = temp;
      }
    }

Here is some tests:

let heap = new Heap();
heap.insert("t")
heap.insert("p")
heap.insert("r")
heap.insert("n")
heap.insert("h")
heap.insert("o")
heap.insert("a")
heap.insert("e")
heap.insert("i")
heap.insert("g")
heap.insert("s")

console.log(heap.isEmpty())
console.log(heap.size())
heap.delMax()
console.log(heap.pq)
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Class named Heap containing pq property seems like heap implemented using priority queue. It should be vice versa. And did you intentionally not implement "build-heap" and "sort-heap" algorithms? And im not sure if a[a.length] = x Is correct, you might want to push instead. \$\endgroup\$ – slepic Sep 3 '20 at 13:19
  • \$\begingroup\$ Good point, yes it should be class PQ and the array this.pq that is the binary heap. The a[a.length] = x works. \$\endgroup\$ – Steven Aguilar Sep 3 '20 at 13:52
  • \$\begingroup\$ It appears that the first element in the array pq is undefined . Is that intentional and/or desired? \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Sep 4 '20 at 12:49
  • 1
    \$\begingroup\$ Yes, is intentional so that the element first element in the heap starts at index 1. Thus making easier to look for parent (k/2) and child (2*k & 2*k + 1) \$\endgroup\$ – Steven Aguilar Sep 4 '20 at 13:59
  • \$\begingroup\$ Your API is somewhat inflexible. A priority queue associates entries with priorities, so the insert operation should be something like insert(value, priority), where priority is some type that has a total order (e.g. number). An alternative that is sometimes used is to instantiate the PQ with a total ordering function, e.g. const pq = new PQ((a, b) => a.length <= b.length), then you could do pq.insert("Hello"), and would get a PQ for strings with priority based on their length. In your implementation, you are using the value also at the same time as the priority and the comparison \$\endgroup\$ – Jörg W Mittag Sep 4 '20 at 21:25
4
\$\begingroup\$

Naming

The name Heap is confusing, since this is a priority queue, not a heap. The heap is merely an internal private implementation detail that should not be exposed to the outside world. Just call it what it is: a PriorityQueue.

The same applies to heap. This one is a local variable with limited scope and obvious semantics, so I would be fine with pq as a name in this case.

Conversely, the pq field actually looks like it is a heap, not a priority queue, so it should probably be named heap.

delMax sounds like the method is deleting the highest priority element, but it is actually popping the highest priority element, i.e. it is returning it. pull, poll, pop, getMax, dequeue are all popular names for this operation.

In fact, in the beginning, I thought you don't even provide this operation at all, since I was led amiss by the name. Even in your own tests, you actually ignore the return value!

Bug

Your isEmpty() method does not return anything. It is evaluating an expression and then throwing away the result. It should be something like this instead:

isEmpty() {
    return this.n === 0;
}

Testing

The above bug is actually caught be the very tests you posted in your question. That seems to indicate that you wrote those tests but are not running them, otherwise you would have noticed.

You should regularly run your tests, ideally in an automated fashion and with automated verification of the results. I run my tests automatically every time I save, every time before I commit to my local Git repository, every time locally before I push to my remote Git repository and then again on the remote repository every time someone pushes to it, every time before and after a merge, every time before a release … you get the idea. Run them as often as possible.

Potential bug?

I have the feeling, although I have not tested it, that your priority queue will not deal well if I want to store null in it.

Triple equals

There is one place where you use the Abstract Equality Comparison Operator == or its negation !=. It is generally best if you forget about its existence and never use it.

Always use the Strict Equality Comparison Operator === or its negation !== instead.

Consistency

Sometimes you use the Abstract Equality Comparison Operator and sometimes the Strict Equality Comparison Operator. Sometimes you use 4 spaces for indentation, sometimes 2. Sometimes you use the term heap and sometimes priority queue (or pq) to refer to the priority queue.

Getters

isEmpty and size should probably be getters instead of normal methods:

get size() {
    return this.n;
}

get isEmpty() {
    return this.n === 0;
}

And the tests need to change accordingly as well:

console.log(pq.isEmpty);
console.log(pq.size);

Use abstractions internally

I am a big fan of using public abstractions also internally. Not everybody agrees with this, though.

So, personally, I would use the size getter in isEmpty instead of accessing the internal n field:

get isEmpty() {
    return this.size === 0;
}

That way, if someone extends your class and overrides some parts of it with a different implementation that doesn't use an n field, isEmpty will still work unchanged.

const over let

When ECMAScript 2015 introduced let and const, the general sentiment was let is the new var, you should always use let. Personally, I disagree, and I think const should be the new var, and you should always const unless you really, really, really need to re-assign it and can't find a way around. Then, and only then, use let.

In your code, heap, max, and temp are never reassigned, so you can use const for them instead.

Class fields

n and pq should probably be class fields. Note that class fields are currently a Stage 3 proposal, which means that while it is highly likely that they will end up unchanged in the ECMAScript Language Specification, they have not been accepted yet and have definitely missed the window for the 2020 release.

class PriorityQueue {
    n = 0;
    pq = [];

    // no constructor needed, all fields already initialized
}

Private methods and fields

swim, sink, less, and exch should be private methods, they shouldn't be part of the public API, same for the class field n.

pq (or heap) should probably also be private. You are using it externally in the tests, but I don't think this is something that should be exposed to the outside world.

class PriorityQueue {
    #n = 0;
    #heap = [];

    get size() {
        return this.#n;
    }

    get isEmpty() {
        return this.size === 0;
    }

    #swim(k) {
        while (k > 1 && this.#less(Math.floor(k / 2), k)) {
            this.#exch(Math.floor(k / 2), k);
            k = Math.floor(k / 2);
        }
    }

    #sink(k) {
        while (2 * k <= this.#n) {
            let j = 2 * k;

            if (this.#heap[j + 1] !== null) {
                if (k > 1 && this.#less(j, j + 1)) {
                    j++;
                }
            }

            if (this.#heap[k] > this.#heap[j]) {
                break;
            }
            this.#exch(k, j);
            k = j;
        }
    }

    insert(v) {
        this.#heap[++this.#n] = v;
        this.#swim(this.#n);
    }

    getMax() {
        const max = this.#heap[1];
        this.#exch(1, this.#n--);
        this.#heap[this.#n + 1] = null;
        this.#sink(1);
        return max;
    }

    #less(i, j) {
        return this.#heap[i] < this.#heap[j];
    }

    #exch(i, j) {
        const temp = this.#heap[i];
        this.#heap[i] = this.#heap[j];
        this.#heap[j] = temp;
    }
}

Note that private methods are also in Stage 3.

API limitations

As currently implemented, the values stored in your priority queue and the priorities assigned to the values are actually the same thing. This is very limiting:

  • You cannot have an ordering of priorities that is different from the natural ordering of the values. For example, you cannot have a priority queue where the priority is based on the length of a string instead of its lexicographic ordering.
  • You can only store values in your priority queue that have a total ordering. Note that in ECMAScript this is trivially true, because all objects are totally ordered with respect to each other, but the ordering is not always intuitive, or do you know offhand what the result of { b: "a", a: "b" } < ["a", 2] is?

Typically, priority queue implementations resolve this in one of two ways:

  1. Each value is associated with a numeric priority.
  2. The priority queue is instantiated with a comparison function that expresses the total ordering relation between the values.

Solution #1 would mean that you change the signature or your insert method to something like this:

insert(v, p)

and then use p as the key for the heap.

Solution #2 would mean that you change the signature of the constructor to something like this:

constructor(f)

and then use f inside less as the comparison function instead of <.

Here is a rough sketch of what that would look like for option #1, the only changes are in insert and less:

insert(v, p) {
    this.#heap[++this.#n] = { element: v, priority: p };
    this.#swim(this.#n);
}

#less(i, j) {
    return this.#heap[i].priority < this.#heap[j].priority;
}

The usage would then look like this:

pq.insert("tally", 2);
pq.insert("plus", 1);
pq.insert("rust", 8);
pq.insert("no", 127);

The version for option #2 would look something like this:

#comparator;

constructor(f) {
    this.#comparator = f;
}

#less(i, j) {
    return this.#comparator(this.#heap[i], this.#heap[j]);
}

And the usage like this:

const pq = new PriorityQueue((a, b) => a.length < b.length);

Further API additions

Being a collection, your priority queue should implement the Iterable interface.

All major data structures in the ECMAScript standard library have methods entries, keys, and values. It makes sense to conform to that interface as well.

\$\endgroup\$
2
\$\begingroup\$

Formatting

The code formatting is fairly consistent in terms of line terminators, though there are a couple lines missing semi-colons - e.g. in swim() and sink(). While they are not always required it is best to be consistent.

Method without return value

The isEmpty method has no return keyword, nor any side effects:

isEmpty() {
  this.n === 0;
}

Presumably it should return that boolean value.

Declaring variables

const can be used for max since it never gets re-assigned. A recommended practice is to default to using const and then when re-assignment is deemed necessary then switch to let. This helps avoid accidental re-assignment.

Swapping values without a temporary variable

One could use Destructuring assignment to swap variables

exch(i, j) {
  [this.pq[i], this.pq[j]] = [this.pq[j], this.pq[i]];
}

However it seems that can be slower than other techniques even though the V8 blog claims "Once we unblocked escape analysis to eliminate all temporary allocation, array destructuring with a temporary array is as fast as a sequence of assignments."1. There is a "hack" suggested in this SO answer by showdev that appears to be the fastest method to swap variables:

this.pq[i] = [this.pq[j], (this.pq[j] = this.pq[i])][0];

Using array length instead of variable n

I could be wrong but it may be possible to eliminate the n variable and just utilize this.pq.length - it may require adjusting things (e.g. manually inserting undefined to the start of the array, etc.).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.