.. highlight:: c++
  :linenothreshold: 5

******************
Heap and Heap Sort
******************

Heap
====
+ Definition

  A complete binary tree in which parent node is always less/greater (min/max
  heap) or equal (if allow overlapped values) than its children

+ Logically a binary complete tree
+ physically an array

  * find parent/children by arithmetic calculation of indices

    - given the node :math:`i`
    - the index of the parent node is :math:`(i-1)/2`
    - the indices of the children nodes are left: :math:`i*2+1` and right:
      :math:`i*2+2`

+ type

  * max heap - root being the greatest value
  * min heap - root being the smallest value

+ behaviors

  * insert

    - insert at the end
    - swap with its parent if it violate the rule (percolate up)
    - keep checking all ancestors till the root is reached

  * remove

    - remove the root by overwriting it using the last element
    - swap the parent node with its least/greatest child starting from the root
      until the leaf node is reached (percolate down)

  * percolate up/down

    - move one element up/down in an existing heap

  * Heap creation

    #. Insert element one by one to a new heap. :math:`\Theta(n \log n)`
    #. Heapify: Percolate down all internal nodes in the order from the last to
       the root :math:`\Theta(n)`

       * repeatedly percolate from the index :math:`size/2-1` to :math:`0`

.. graphviz::
  :caption: A max heap (tree form)

  digraph tree {
    26 -> {25 17}[color=red];
    25 -> {7 19}[color=green];
    17 -> {2 4}[color=blue];
    7 -> {1 5}[color=violet];
  }

.. graphviz::
  :caption: A max heap (array form)

  digraph arr {
    node[shape=record];
    arr[label="<f0> 26|<f1> 25|<f2> 17|<f3> 7|<f4> 19|<f5> 2|<f6> 4|<f7> 1|<f8> 5"];
    arr:f0:n -> arr:f1:n[color=red];
    arr:f0:n -> arr:f2:n[color=red];
    arr:f1:s -> arr:f3:s[color=green];
    arr:f1:s -> arr:f4:s[color=green];
    arr:f2:s -> arr:f5:s[color=blue];
    arr:f2:s -> arr:f6:s[color=blue];
    arr:f3:n -> arr:f7:n[color=violet];
    arr:f3:n -> arr:f8:n[color=violet];
  }

Applications
============
+ Heap sort
+ Priority queue

Visualization
=============
+ http://www.cs.usfca.edu/~galles/visualization/Heap.html
+ https://visualgo.net/en/heap

Priority queue
==============
* Not really a queue or stack because the dequeue order is not related to the
  enqueue order
* any in min/max out
* behaviors mostly same as a queue

  - enqueue
  - dequeue
  - peek
  - isEmpty
  - length

* Implementations

  - **heap** best
  - sorted array, sorted insert to insert
  - sorted linked-list, sorted insert to insert