***************************
Topic 10b - Priority Queues
***************************

You should already know what a queue is.

For those who don't it is an ADT that store elements in the order they arrive.

Queues implement a FIFO (First In First Out) strategy.

However, elements need to be dealt in priority.

.. admonition:: Activity
    :class: warning

    *  Do you have an idea of applications that requires to process some elements in priority without changing the global FIFO strategy?


In this topic we will discuss and implement a priority queue.

Model
=====

A Priority Queue is an ADT that has the two following operations:

*  Insertion: Inserts a new element
*  DeleteMin: Find, return and remove the minimum element in the queue

As in many ADT you can add more operations.

Priority Queues have many applications, especially in greedy algorithms.

Simple implementations
======================

We could think of a very simple implementation of a priority queue.

.. admonition:: Activity
    :class: warning

    *  Discuss and come up with a simple implementation.
    *  What is the complexity for insertion? Deletion?


When we say simple implementation, we usually think **Linked List**.

If we have a liked list:

*  Insertion: :math:`O(1)`
*  DeleteMin: :math:`O(N)`

.. admonition:: Activity
    :class: warning

    *  Why is the deletion :math:`O(N)`?


We want to delete the minimum element, thus to reduce the complexity we could use a sorted linked list.

If we consider a sorted list:

*  Insertion: :math:`O(N)`
*  DeleteMin: :math:`O(1)`

So, neither implementation is  very efficient.

.. note::

    The first implementation is better, as in average you're inserting more than you're deleting.


Binary Heap
===========

**Binary Heap** is the most popular implementation of this ADT.

Usually we call priority queues **heaps**.

Structure
---------

A heap is a binary tree that is completely filled with the possible exception of the bottom level.

.. note::

    By definition it is a complete binary tree.


An example of a complete binary tree.

.. figure:: ../img/topic10/complete_binary_tree.png
    :align: center


As a complete binary tree is regular, it is very easy to represent in an array.

.. figure:: ../img/topic10/array_implementation.png
    :align: center


We can take any element in the array at position :math:`i`:

*  The left child is at position :math:`2i`.
*  The right child is at position :math:`(2i + 1)`.
*  The parent is in position :math:`\lfloor i/2\rfloor`.

.. admonition:: Header file
    :class: dropdown

    .. code-block:: cpp
        :linenos:

        template<typename Comparable>
        class BinaryHeap{
            public:
                BinaryHeap(int capacity = 100);
                BinaryHeap(const vector<Comparable>& items);

                void insert(const Comparable& x);
                void deleteMin();
            
            private:
                int curentSize;
                vector<Comparable> array;
        };


Heap-Order Property
-------------------

The **Heap-Order** property allows operations to be performed quickly.

To find the minimum element quickly, it needs to be at the root.

The heap-order property:
    For every node :math:`X`, the key in the parent of :math:`X` is smaller than (or equal to) the key in :math:`X`, with the exception of the root.

The following is a good illustration of a heap:

.. figure:: ../img/topic10/two_trees.png
    :align: center

    The left tree is a heap, the right tree is not.

Basic Operations
----------------

The two basic operations are simple to implement.

insert
******

To insert an element :math:`X`:

*  Create a hole in the next available location
*  If placing :math:`X` in the hole violates the heap-order condition.

   *  Put the parent's hole in the hole, and :math:`X` at the parent's position.
   *  Otherwise place :math:`X` in the hole.

*  It continues until :math:`X` can be placed in a hole.

.. admonition:: Example
    
    *  Consider the following tree.
    *  We want to insert the number :math:`14`.

    .. figure:: ../img/topic10/insert_00.png
        :align: center

    *  We're creating a hole for 14.
    *  As it would break the heap-order property, we place the parent (:math:`31`) in the hole instead.

    .. figure:: ../img/topic10/insert_01.png
        :align: center

    *  We continue the process.

    .. figure:: ../img/topic10/insert_02.png
        :align: center

.. admonition:: Activity
    :class: warning

    *  Insert 5, 59 and 10 in the previous binary heap.
    *  Draw the tree after each step.

.. admonition:: Implementation
    :class: dropdown

    .. code-block:: cpp
        :linenos:

        void insert(const Comparable& x){
            if (currentSize == array.size() - 1){
                array.resize(array.size() * 2);
            }
            int hole = currentSize++;
            Comparable copy = x;
            
            array[0] = copy;
            for ( ; x < array[hole/2]; hole /= 2){
                array[hole] = array[hole/2];
            }

            array[hole] = array[0];
        }

The time complexity of the insertion in the worst-case :math:`O(\log N)`.


deleteMin
*********

Finding the minimum is easy, but removing it is hard.

*  When a minimum is removed, a hole is created.
*  We should place the last element in the heap :math:`X` in the hole.
*  If we can place it, we're done otherwise
*  We slide the smaller children in the hole.
*  We continue until :math:`X` can be placed in the hole.


.. admonition:: Example
    
    *  Consider the previous tree.
    *  We want to delete the number 13.
    *  It creates a hole, 31 the last element cannot be inserted.

    .. figure:: ../img/topic10/delete_01.png
        :align: center

    *  We're move 14 up to fill the hole.
    *  Inserting 31 would break the heap-order property, so we place the smaller children (19) in the hole instead.

    .. figure:: ../img/topic10/delete_02.png
        :align: center

    *  We continue the process.

    .. figure:: ../img/topic10/delete_03.png
        :align: center


We call this strategy **percolating down**.

.. admonition:: Activity
    :class: warning

    *  Delete 14 and draw the tree after each step.


.. admonition:: Implementation
    :class: dropdown

    .. code-block:: cpp
        :linenos:


        Comparable deleteMin(){
            array[1] = array[currentSize--];
            percolateDown(1);
        }

        void percolateDown(int hole){
            int child;
            Comparable tmp = array[hole];

            for ( ; hole*2 <= currentSize; hole = child){
                child = hole * 2;
                if ( child != currentSize && array[child + 1] < array[child]){
                    ++child;
                }
                if (array[child] < tmp){
                    array[hole] = array[child];
                }
                else{
                    break;
                }

            }
            array[hole] = tmp;
        }

The time complexity in the worst-case is :math:`O(\log N)`.

In average it is also :math:`O(\log N)`.