priorityQueue does not poll out as expected

[zonglinlee]

describe('priorityQueue Test:', () => {
 it('should return correct priorityQueue results:', () => {
    const pq = new PriorityQueue();
    pq.add(1);
    pq.add(2);
    pq.add(3);
    pq.add(4);
    expect(pq.toString()).toBe('1,2,3,4');
    expect(pq.poll()).toBe(1);
    expect(pq.poll()).toBe(2);
    expect(pq.poll()).toBe(3);
    expect(pq.poll()).toBe(4);
  });
});

now it poll out 1, 4, 3, 2, expected: 1,2,3,4

[stiven104]

They have a writing error, the correct one is "if" and not 'it'.

[PranjalPatel14]

You need to show me the poll method in priorityQueue? I think issue is occured due to that thing.

[v-a14]

Is this issue is still open ?

[fahad-ejaz]

The priority queue extends the heap Class. The poll() method, inherited by the priority queue class, is part of the Heap Class. I have pasted a portion of the code from the method below:

// Move the last element from the end to the head.
    this.heapContainer[0] = this.heapContainer.pop();
    this.heapifyDown();

As you can see, the poll method pushes the last element in the queue to the front. In your case, after the first element is 'polled', the last element, which is 4, will be moved to the front of the queue. The 'heapifyDown' method, then, sorts the queue based on a comparator function. The priority queue class overrides the compactor function of the heap Class to ensure the queue is sorted based on priority of the item and not its value.

this.compare = new Comparator(this.comparePriority.bind(this));

comparePriority(a, b) {
    if (this.priorities.get(a) === this.priorities.get(b)) {
      return 0;
    }
    return this.priorities.get(a) < this.priorities.get(b) ? -1 : 1;
  }

Since the priorities of all the items in the queue are the same, the 'heapifyDown' method does not sort the queue after 4 is moved to the front.

So if you were to log the output of the toString method:

pq.poll()
console.log(pq.toString())

Output: '4,3,2'

instead of '2,3,4'

If you are not going to assign priorities to the items in the queue, try using the minHeap data structure. When you use that data structure, the 'heapifydown' method will sort the queue based on the value of the item. You would get the output you were expecting.