**__2.5: A More Complex Data Structure: Priority Queues__**

One of the book's key focuses is to seek algorithms that improve qualitatively on brute-force search, and the priority queue can help a lot with this.

A priority queue is a first in first out collection that allows ordering by priority.  This can be useful in real-time events such as the scheduling of processes on a computer.  Each process has a priority, but process do not arrive in order of their priorities.  

__A Data Structure for Implementing a Priority Queue__

Heaps are used in the implementation of Priority Queues - balanced binary trees in which each child is at at least as large as its parent's.
When adding/removing items from this heap we need to order them as well in a logn time - this calls for algorithms that iterate in the worst case through the heap's height.  
When needing to travel up the heap:
  Heapify-up(H, i):
  
  if i > 1 then
    let j = parent(i) = [i/2]
    if key[H[i]]<key[H[j]] then
      swap the array entries H[i] and H[j]
      Heapify-up(H, j)

this swaps the child/parent when the child is smaller than the parent, thus moving it up the tree @ O(logn) runtime.

When needing to travel down the heap:
  Heapify-down(H, i):
  
  Let n = length(H)
  If 2i> n then
    terminate with H unchanged
  else if 2i< n then
    Let left = 2i and right 2i+1  
    Let j be the index that minimizes key[H[left]] and key[H[right]]
  else if 2i == n then
    Let j = 2i
  if key[H[j]] < key[H[i]] then
    swap the array entries H[i] and H[j]
    Heapify-down(H, j)

this swaps the child/parent when the parent is bigger than the child.  

Here is a list of the runtimes of heap operations:
  * StartHeap(N) returns an empty heap H that is set up to store at most N elements.  O(n).
  * Insert(H, v) inserts the item v into heap H.  If the heap currently has n elements, O(logn).
  * FindMin(H) identifies minimum element.  O(1).
  * Delete(H, i) deletes the element in heap position i. O(logn).
  * ExtractMin(H) identifies and deletes an element with the minimum key value from a heap.  This combines delete and FindMin - O(logn).

This section was interesting and helped me learn the runtimes of the heap much better.
10/10.