1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
[\<- 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
|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.
---
[05/18 ->](05-18.md)
|
