*************************
Heaps and 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, sometimes elements need to be dealt in priority.

.. admonition:: Activity
    :class: activity

    *  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
*  Delete: 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: activity

    *  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 linked list:

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

.. admonition:: Activity
    :class: activity

    *  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/complete_binary_tree.png
    :align: center


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

.. figure:: ./img/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`.

It gives us the following structure of the ADT:

    .. literalinclude:: ./OPriorityQueue.java
        :language: java
        :linenos:
        :lines: 6-32, 49-67, 79, 102-109, 143, 185


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/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
    :class: example
    
    *  Consider the following tree.
    *  We want to insert the number :math:`14`.

    .. figure:: ./img/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/insert_01.png
        :align: center

    *  We continue the process.

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

.. admonition:: Activity
    :class: activity

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

.. admonition:: Implementation
    :class: dropdown

    .. literalinclude:: ./OPriorityQueue.java
        :language: java
        :linenos:
        :lines: 49-79

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
    :class: 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/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/delete_02.png
        :align: center

    *  We continue the process.

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


We call this strategy **percolating down**.

.. admonition:: Activity
    :class: activity

    *  Delete 14 and draw the tree after each step.


.. admonition:: Implementation
    :class: dropdown, note

    .. literalinclude:: ./OPriorityQueue.java
        :language: java
        :linenos:
        :lines: 102-143

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

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