Data structures - create a priority queue class

Hi,

There’s a problem with this lesson. In the instructions:

Item priority will override placement order in determining the sequence items are dequeued. If an item with a higher priority is enqueued after items with lower priority, the higher priority item will be dequeued before all the others.

In the hint:

  • In this challenge we need to create a Priority Queue class based on Min-Heap with a few methods:
    • enqueue() - It enqueue’s the new node to it’s appropriate place in queue.
    • dequeue() - It removes the first node from the queue.
    • front() - This method returns the first node to be dequeued.
    • size() - Returns the size of the queue.
    • isEmpty() - Returns if the queue is empty.

I’m confused as to whether we should be enqueuing according to priority or dequeuing according to priority. I’d appreciate it if this could be cleared up and the instructions/hint adjusted accordingly.

link to lesson

please provide a link to the lesson you are referring to

sorry about that, I added it to the original post.

the objective is to dequeue according to priority.

A possible way to do that is to enqueue according to priority…
But there are other ways to handle it as well.

Items of higher priority (lower priority number) should be dequeued before items of lower priority, but items of the same priority should be dequeued in the order that they were enqueued.

If we use the following test:

function testProrityQueue(){
  const pq = new PriorityQueue();
  pq.enqueue(['cat',5]);
  pq.enqueue(['giraffe',3]);
  pq.enqueue(['bear',5]);
  pq.enqueue(['dog',1]);
  pq.enqueue(['mouse',3]);
  pq.enqueue(['snake',1]);

  while (!pq.isEmpty()){
    console.log(pq.dequeue());
  }
}

testProrityQueue();

We should get this output:

dog
snake
giraffe
mouse
cat
bear

Thanks for your reply. That sounds reasonable if the tests are unopinionated about where the prioritizing logic would be, but it might cause trouble with the front method if it expects a specific item:

The front method should return the correct item at the front of the queue as items are enqueued and dequeued.

My prioritizing logic is in my dequeue method, FYI. Here is the code:

function PriorityQueue () {
    this.collection = [];
    this.printCollection = function() {
      console.log(this.collection);
    };
    // Only change code below this line
    this.enqueue = (item) => {
      this.collection.push(item);
    };
    this.dequeue = () => {
      let removedItem;
      let removalIndex;
      let topPriority;
      this.collection.forEach((item, index) => {
        const [name,priority] = item;
        if(!topPriority) {
          topPriority = priority;
          removalIndex = index;
          removedItem = name;
        };
        if(priority<topPriority){
          topPriority = priority;
          removalIndex = index;
          removedItem = name;
        };
      });
      this.collection.splice(removalIndex,1);
      return removedItem;
    };
    this.front = () => {
        const [name, _] = this.collection[0];
        return name;
    };
    this.isEmpty = () => {
      return this.collection.length === 0;
    };
    this.size = () => {
      return this.collection.length;
    };
    // Only change code above this line
  }

EDIT: I have corrected the dequeue method so that the output is correct but I still get the error mentioned above for the front method.

Thanks for the nifty test function, I see that there’s a problem with my dequeue method.

EDIT: I have now corrected my dequeue method so that the output is in line with that of bvanb’s post but I still get the error mentioned above with front.

I can now confirm that the item needs to be enqueued according to priority.

1 Like