PriorityQueue Internals

0

PriorityQueue is based on balanced binary heap tree data structure in which all the nodes of the tree are in a specific order. Internally the node values are stored in an array. Properties are:

  1. The head of this queue will have the the least element with respect to the specified ordering.
  2. Both the subtrees (left and right) to a node have values greater than the node,  Left node > Parent node < Right node
  3. If queue[i]is the parent node then the left node would be stored in queue[2*i + 1] and the right node would be in queue[2*(i + 1)]

The order is defined using comparator. Either the node type must be Comparable or one needs to pass in the Comparator so that the nodes can compare with each other.

PriorityQueueExample:

package com.javarticles.collections;

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue();
        pq.add(37);
        pq.add(20);
        pq.add(40);
        pq.add(15);
        pq.add(35);
        pq.add(50);
        pq.add(30);
        pq.add(25);
        pq.add(29);
        pq.add(10);
        System.out.println(pq);
        pq.remove(15);
        System.out.println("After removal of 15" + pq);
        pq.remove(10);
        System.out.println("After removal of 10" + pq);
    }
}

Output:

[10, 15, 30, 25, 20, 50, 40, 37, 29, 35]
After removal of 15[10, 20, 30, 25, 35, 50, 40, 37, 29]
After removal of 10[20, 25, 30, 29, 35, 50, 40, 37]         

Sift up

Whenever a new node is added, it is added as far to the ‘left’ as possible.

The new value is placed in this node.

We then check if the resulting tree is a heap: the place chosen for the new node guarantees that the structural property will be satisfied, but the ordering property might be be violated. The ordering property is re-established by the `SIFT UP’ operation.

The `SIFT UP’ operation starts with a value in a leaf node. It moves the value up the path towards the root by successively exchanging the value with the value in the node above. The operation continues until the value reaches a position where it is less than its parent, or, failing that, until it reaches the root node.

 

If you notice, all the levels are full, except perhaps the bottom level.

Adding more elements

We will now add 35, 50, 30, 25 and 29

Sift Up Algorithm

In this section, we will see how sift up works.

We will now add 10 to the above queue.

An attempt will be made to add it to the last index, which is the size itself. Since size is 10, index k where we will try to add the new value is 10, parent is (k-1)/2, which is 4.

Instead of actually adding the value, we will first check whether its parent, which is Q[4] is lesser than the node value or not. Only if it is lesser that we will add else we will check its parent and so forth. Since parent value is 35 is which is greater than 10, we can’t add, and instead we move the parent value 35 to index k. After moving we will set k to 4.

We proceed the same steps again. Parent of Q[4] is Q[1] which is 20 here. Since 20 is greater than 10, we will move 20 to Q[4], set k to 1 and then check Q[1]s’s parent. Q[1]’s parent is the root node which is 15. Again 15 is greater than 10 so we move 15 to Q[1] and set k=0. We now find 10 which is root value is lesser than Q[1] which is 15 so we end here and assign 10 to the root which is the first element.

Since the subtrees have higher value than the parent node, every path in a heap is a sorted list. For example, 10-15-25-29

Sift Down

Let’s delete node 15.

In order to make sure the rules are intact we do a sift down which is exactly opposite of sift up.

We move the last value 35 to the node that 15 occupies. Since it is greater than the subtrees, we again exchange the smaller of its children, in our case 20.

Thus successive exchange of the value with the smaller of its two children is the operation . The operation continues until the value reaches a position where it is less than both its children, or, failing that, until it reaches a leaf.

Next we will delete node 10.

Share.

Comments are closed.