=====================================
7-Priority Queues and Heaps
=====================================

Summary
-------
Priority queues return items by priority (not insertion order).  
Heaps are the common data structure used to implement priority queues efficiently,  
supporting fast lookup of the highest (or lowest) priority and dynamic insert/remove operations.

Priority Queues
---------------
- Store items with an associated priority score.
- Common operations:
  
  * ``insert(item, priority)`` — add an item.
  * ``peek()`` — return highest-priority item (null if empty).
  * ``remove()`` — remove & return highest-priority item (null if empty).
  * ``is_empty()``, ``size()``.

- Use cases: packet scheduling, spellcheck suggestions, best-first search,  
  task triage (e.g., ER), ranked recommendations.

Implementations & Trade-offs
----------------------------
- **Sorted list/array**: ``peek()`` O(1), ``insert()`` O(N) (must place new item in order).
- **Unsorted list/array**: ``insert()`` O(1), ``peek()`` / ``remove()`` O(N) (must scan).
- **Heap**: balances costs — ``peek()`` O(1), ``insert()`` O(log N), ``remove()`` O(log N).  
  Good when both insertions and extractions are frequent.

Heaps (Max-Heap)
----------------
- **Heap property (max-heap)**: each node ≥ its children. Root = maximum.
- **Array representation** (packed array, root at index 1):

  * Left child of node at ``i`` → ``2*i``
  * Right child → ``2*i + 1``
  * Parent of node at ``i`` → ``floor(i / 2)``

- Keep ``array_size`` and ``last_index`` (virtual end). Preallocate to avoid frequent resizes.

Heap Insert (Bubble Up)
-----------------------
.. code-block:: none

   HeapInsert(heap, value):
       if heap.last_index == heap.array_size - 1:
           increase heap size
       heap.last_index += 1
       heap.array[heap.last_index] = value
       current = heap.last_index
       parent = floor(current / 2)
       while parent >= 1 and heap.array[parent] < heap.array[current]:
           swap(heap.array[parent], heap.array[current])
           current = parent
           parent = floor(current / 2)

- Worst-case swaps ≈ tree height → O(log N).

Remove Max (Bubble Down)
------------------------
.. code-block:: none

   HeapRemoveMax(heap):
       if heap.last_index == 0:
           return null
       result = heap.array[1]
       heap.array[1] = heap.array[heap.last_index]
       heap.array[heap.last_index] = null
       heap.last_index -= 1
       i = 1
       while i <= heap.last_index:
           swap = i
           if 2*i <= heap.last_index and heap.array[swap] < heap.array[2*i]:
               swap = 2*i
           if 2*i+1 <= heap.last_index and heap.array[swap] < heap.array[2*i+1]:
               swap = 2*i+1
           if i != swap:
               swap(heap.array[i], heap.array[swap])
               i = swap
           else:
               break
       return result

- Also O(log N) worst-case.

Storing Auxiliary Info / Comparators
------------------------------------
- Store records (e.g. ``TaskRecord { priority, data... }``).
- Use a comparator helper (e.g. ``IsLessThan(a, b)``) instead of raw ``<``  
  so heap works for composite types.

Updating Priorities
-------------------
- ``UpdateValue(heap, index, new_value)``:
  
  * Replace value
  * If new > old → bubble up
  * Else → bubble down

- Finding an element’s index is not efficient in a heap;  
  use a secondary map (hash table) to track item → heap index if updates by key are needed.

Min-Heap
--------
- Same structure but property reversed: parent ≤ children.
- Implementation is identical except comparisons use ``>`` instead of ``<``.
- (Or negate priorities as a quick trick.)

Heapsort
--------
- Two phases:

  1. Build heap from all items.
  2. Repeatedly ``remove_max`` to produce sorted output  
     (decreasing for max-heap).

- Simple approach (insert all then extract all) gives:

  * Build: O(N log N)
  * Extraction: O(N log N)
  * Overall: O(N log N)

Complexity Summary
------------------
- ``peek()`` (root lookup): **O(1)**
- ``insert()``: **O(log N)** worst-case
- ``remove()`` (max/min): **O(log N)** worst-case
- Build by repeated inserts: **O(N log N)**
- Heapsort: **O(N log N)**
- Space: **O(N)** (packed array)

Why It Matters
--------------
Heaps trade off searchable structure for prioritized retrieval and  
dynamic insert/remove efficiency. They keep the tree nearly complete  
so path lengths are small (≈ log N), making both insertion and extraction fast.  
Use heaps when you need frequent prioritized access but not arbitrary-value search.


.. literalinclude:: priority_heap.cpp
   :language: cpp 

.. literalinclude:: priority_heap.py
   :language: python