A priority queue is a data structure that can be represented by a tree and by an array. There are some distinct properties of a priority queue tree. Observe the tree below:

                  3
         19            8
   23        25     24   18
37   26    30  29

Property 1: The parent is smaller than both children. Observe above that 3 is smaller than 19 and 8 and is their parent.

Property 2: The tree is filled from top to bottom and left to right. If you wish to add a new node, it goes to the current bottom level of the tree all the way to the right.

Property 3: The root has the highest priority of them all. Notice that the tree is in order from smallest to greatest. Think of the US Military and the DEFCON system. DEFCON 5 is the least serious while DEFCON 1 is the most serious.

Insertions

So say that we wanted to insert into the tree. Let’s follow the algorithm below for insertion into the priority queue.

Algorithm for insert:
1. Place the new element at the end of the tree.
2. "Bubble up" the new element:
    a. Compare the new element to the current parent.  IF parent > element, SWAP the elements.
    b. REPEAT UNTIL Parent < element or you are at the root of the tree.

Let's see an insertion into the tree above (number bolded to denote an insertion):

                  3
         19            8
   23        25     24   18
37   26    30  29 17

Compare 17 with 24. Here, swap the elements. The tree now looks like:

                  3
         19                8
    23       25       17     18
37    26  30    29  24

Compare 17 with 8. Here, DO NOT swap those elements since the parent (8) is less than the child (17).

Deletion

Now that we know how to insert, let’s see how to delete.

Since a priority queue tree is in sorted order, we should only remove from the root of the tree since the goal is to keep it in sorted order.

Algorithm for deletion:
1. Remove and output the root of the tree.
2. Take the current last element and place it at the root of the tree.
3. "Bubble down" that element:
        a. Pick the minimum child.
        b. Compare the minimum child with the parent and swap them if the child is < parent.
        c. REPEAT UNTIL at the bottom OR parent < children.

Using the tree from before, let’s perform a deletion from it:

                  3
         19                8
    23       25       17     18
37    26   30   29  24

The root of 3 gets removed and the element 24 goes in its place:

                  24
         19                8
    23       25       17     18
37     26  30  29

Select the minimum child (8) and compare them. Here, swap the elements since 8 is less than 24.

                  8
         19                24
    23       25       17      18
37    26  30   29

Select the minimum child (17) and compare them. Here, swap the elements since 17 is less than 24.

                  8
         19                17
    23       25       24       18
37    26  30   29

You are at the bottom so you are now finished. You have performed a correct deletion.

Array representation

Coming soon....