Priority Queue
**********************

Priority queue is a weighted queue. Since it is a queue, it allows you to add, delete, and peek element, but nothing else. In most cases, priority queue is implemented as a binary heap tree. Heap tree is **complete tree**, so the index can be calculated if all the nodes are stored in a sequential array. (Complete means there is no hole inside the tree.)

.. figure:: maxheap.png
  :align: center
  :name: max_heap

  A max binary heap tree stored a flat array


In C++, a 0-based array is used as the underlying data structure, the indexing scheme is:

.. literalinclude:: index_heap.h
  :language: c++
  :linenos:
  :lines: 7-9

If parent node index is i, left child index is 2i+1, and right child index is 2i+2.
If child index is i, the parent index is (i-1)/2. (Refer to how segement tree makes this easier at :numref:`subarray_minimum_query`)


- Heap Node Comparator

Unlike map or set, defining a less-than operator< inside the object class doesn't work for priority_queue. You need to use a separate comparator class with an ``operator()`` method.

.. literalinclude:: remove_smallest_peaks_in_order_test.cpp
  :language: c++
  :linenos:
  :lines: 11-13
  :emphasize-lines: 4

This way you have to use the comparator as a template argument when declaring the priority queue.

.. literalinclude:: remove_smallest_peaks_in_order_test.cpp
  :language: c++
  :linenos:
  :lines: 16

There are other ways like using lambda, or overload the **less-than operator** globally.

|:feet:| The time complexity of building a heap is linear!

The following are a list advanced algorithms or applications using priority queue:

- Beam Search
- Heavy Hitters(top-k problem)
- K-way Merge
- Dijkstra algorithm for weighted graph
- Huffman Coding
- Prim's Algorithm
- Job scheduling and interrupt handling.

----

Heap seems very similar to **segment tree**, but actually they are very different. All heap nodes are from input. For segment tree, only leaves are from input, and inner nodes are result of computing.

Another data structure similar to heap is **Young Tableau**.

.. toctree::
    :maxdepth: 2

    dheap
    index_heap
    questions
    extra