Post-class 05/15

3 files changed, 103 insertions, 0 deletions

diff --git a/05-13.md b/05-13.md
index 13e8970..8b53a35 100644
--- a/05-13.md
+++ b/05-13.md
@@ -212,3 +212,7 @@ NODE *deleteNODE(NODE *root, int x, bool *found){
 |**Add**        |O(n)          |O(n)        |O(n)      |O(n)                |O(n)                               |O(h) (log(n) <= h <= n)|
 |**Remove**     |O(n)          |O(n)        |O(n)      |O(n)                |O(n)                               |O(h) (log(n) <= h <= n)|
 |**Min/Max**    |O(n)          |O(1)        |O(m)      |O(n)                |O(1) (assuming fast access to tail)|O(h) (log(n) <= h <= n)|
+
+---
+
+[05/15 ->](05-15.md)
diff --git a/05-15.md b/05-15.md
new file mode 100644
index 0000000..9a34c34
--- /dev/null
+++ b/05-15.md
@@ -0,0 +1,99 @@
+[\<- 05/13](05-13.md)
+
+---
+
+# Priority Queue
+
+In a priority queue, an element with **high priority** is served before an element with low priority. If two elements have the same priority, they are served **according to their order** in the queue
+
+### Example
+
+- A priority queue example: Emergency room
+	- FIFO
+	- in case of emergency, a patient can be given priority
+
+## Priority Queue & Queue
+
+- In a queue, all the keys are ordered only according to when they enter the queue. Such order is not related to their priorities (e.g. values)
+
+- In a priority queue, both the **key priorities** (e.g. values) and **their order** of entering the queue are considered. In addition, priority plays a more important role
+
+## Implementation
+
+- Assume you are required to organize a sequence as 5,20,18,10,3,18,20 in a priority queue. What is the dequeue sequence? (i.e. lower value indicating higher priority)
+	- 3, 5, 10, 18, 18, 20, 20
+
+- How to implement a priority queue?
+	- Can we use sorted array? What are the worst-case big-O for enqueue and dequeue?
+		- Enqueue will involve shifting -> O(n)
+		- Dequeue can function as a circular queue -> O(1)
+	- Can we use sorted linked list? What are the worst-case big-O for enqueue and dequeue?
+		- Enqueue involves traversal -> O(n)
+		- Dequeue is O(1)
+		- No benefits with linked list
+	- Can we do better? YES
+		- **Binary Heap**
+
+# Heap
+
+- A heap is a **binary tree** with two properties:
+	1. It's a complete (or nearly complete) tree in that it is built left-to-right and top-down (the shape)
+	2. It's heap ordered: the root of every subtree is the **maximum value** in that subtree (the order)
+
+- Technically these are called "max heaps" and we can also have "min heaps"
+
+## Insertion
+
+- The largest value in a binary max-heap is always the **root**
+- Q: How do we insert a value into a max heap?
+- A: We
+	- insert the new node so as to **not break the shape of the tree**
+	- We might **break the heap order**, so we then fix it
+
+- To not break the shape, we insert the new node as the **next leaf from left to right** on the lowest level
+- This may break the heap order, so we **fix the heap** nodes by repeatedly swapping the new value with its new parent - We call this process as reheap up
+- ex. insert 30, 70, 50, 10, 20, 80, 40
+- What is the big O?
+	- O(h)
+
+- Insertion is O(h), but h is always log(n), so insert is O(log(n))
+
+## Deletion
+
+- Q: How do we delete a value from a heap?
+- A: We must first find it, so **we generally always delete the maximum value** because it's at the root
+	- We first replace the root with the last value on the lowest level, so as to preserve the shape
+	- This process may break the heap order, so we fix it by repeatedly swapping the upstart value with its larger child. Why not smaller child?
+	- "reheap down"
+
+- What is big O?
+	- O(h) = O(log(n))
+
+- Deletion (of the root) is also O(log(n))
+
+## Implementation
+
+- We will implement our heap using an **array**
+- Let's look at implementing a heap
+
+![heap example](05-15_img1.png)
+
+|Value    |44|18|33|6|14|32|27|-|-|
+|---------|--|--|--|-|--|--|--|-|-|
+|**Index**|0|1|2|3|4|5|6|7|8|
+
+- Specifically, if the parent's node's index is i
+	- left child is of i is `2*i + 1`
+	- right child of i is `2*i + 2`
+	- parent of i is `(i-1)/2`
+
+- Example: Node 14 -> index = 4
+	- parent should be index `(4-1)/2)` = 1
+
+binary heaps work because of **no holes**, and are a great example of an implicit data structure that uses no extra space to let you know where everything is
+
+## When to use Heap?
+
+- Generally speaking, a heap can be used whenever you need **quick access** to the largest (or smallest) item, because that item will always be the first element in the array or at the root of the tree
+- It's not good for searching, since the remainder of the array is kept partially unsorted
+- Some examples of heap: priority queue, Huffman coding, heap sort, etc.
diff --git a/05-15_img1.png b/05-15_img1.png
new file mode 100644
index 0000000..b371935
--- /dev/null
+++ b/05-15_img1.png