DSA 13: Intro to Heaps
NBIT209/DIFT204 Data Structures and Algorithms
PAUL OFFEI
1
NBIT209/DIFT204
NBIT209/DIFT204
1
Warm Up
What is the resulting LLRB after inserting 22 into the tree below?
What is the resulting LLRB after inserting 67 into the tree below?
Left Rotation
Right Rotation
NBIT209/DIFT204
2
Priority Queue ADT
Binary Heap
Binary Heap Methods
NBIT209/DIFT204
3
A new ADT!
Imagine you’re managing a queue of food orders at a restaurant, which normally takes food orders first-come-first-served.
Suddenly, NSBT Director walks into the restaurant!
You realize that you should serve her as soon as possible (to gain political influence or so that she leaves the restaurant as soon as possible), and realize other celebrities could also arrive soon. Your new food management system should rank customers and let us know which food order we should work on next (the most prioritized thing).�
NBIT209/DIFT204
4
Priority Queue ADT
Min Priority Queue ADT
removeMin() – returns the element with the smallest priority, removes it from the collection
state
behavior
Set of comparable values
- Ordered based on “priority”
peekMin() – find, but do not remove the element with the smallest priority
add(value) – add a new element to the collection
Perfect for our NSBT Director food order situation
Other uses:
NBIT209/DIFT204
5
Priority Queue ADT
Min Priority Queue ADT
removeMin() – returns the element with the smallest priority, removes it from the collection
state
behavior
Set of comparable values
- Ordered based on “priority”
peekMin() – find, but do not remove the element with the smallest priority
add(value) – add a new element to the collection
Max Priority Queue ADT
removeMax() – returns the element with the largest priority, removes it from the collection
state
behavior
Set of comparable values
- Ordered based on “priority”
peekMax() – find, but do not remove the element with the largest priority
add(value) – add a new element to the collection
If a Queue is “First-In-First-Out” (FIFO) Priority Queues are “Most-Important-Out-First”
Items in Priority Queue must be comparable – �The data structure will maintain some amount of internal sorting, in a sort of similar way to BSTs/AVLs
NBIT209/DIFT204
6
Implementing Priority Queues: Take I
Implementation | add | removeMin | Peek |
Unsorted Array | | | |
Linked List (sorted) | | | |
AVL Tree | | | |
Maybe we already know how to implement a priority queue.
How long would removeMin and peek take with these data structures?
For Array implementations, assume you do not need to resize.
Other than this assumption, do worst case analysis.
NBIT209/DIFT204
7
Implementing Priority Queues: Take I
Implementation | add | removeMin | Peek |
Unsorted Array | 𝚹(1) | 𝚹(n) | 𝚹(n) |
Linked List (sorted) | 𝚹(n) | 𝚹(1) | 𝚹(1) |
AVL Tree | 𝚹(log n) | 𝚹(log n) | 𝚹(log n) |
Maybe we already know how to implement a priority queue.
How long would removeMin and peek take with these data structures?
For Array implementations, assume you do not need to resize.
Other than this assumption, do worst case analysis.
NBIT209/DIFT204
8
Implementing Priority Queues: Take I
Implementation | add | removeMin | Peek |
Unsorted Array | 𝚹(1) | 𝚹(n) | 𝚹(n) 𝚹(1) |
Linked List (sorted) | 𝚹(n) | 𝚹(1) | 𝚹(1) |
AVL Tree | 𝚹(log n) | 𝚹(log n) | 𝚹(log n) 𝚹(1) |
Maybe we already know how to implement a priority queue.
How long would removeMin and peek take with these data structures?
Add a field to keep track of the min. �Update on every insert or remove.
AVL Trees are our baseline – let’s look at what computer scientists came up with as an alternative, analyze that, and then come back to AVL Tree as an option later
NBIT209/DIFT204
9
Priority Queue ADT
Binary Heap
Binary Heap Methods
NBIT209/DIFT204
10
Heaps
Idea:
In a BST, we organized the data to find anything quickly. (go left or right to find a value deeper in the tree)
Now we just want to find the smallest things fast, so let’s write a different invariant:
Heap invariant �Every node is less than or equal to both of its children.
6
5
4
8
7
373
4
5
6
7
In particular, the smallest node is at the root!
Do we need more invariants?
NBIT209/DIFT204
11
Heaps
With the current definition we could still have degenerate trees.
From our BST / AVL intuition, we know that degenerate trees take a long time to traverse from root to leaf, so we want to avoid these tree structures.
The BST invariant was a bit complicated to maintain.
4
5
6
7
a degenerate tree
…
NBIT209/DIFT204
12
Heaps
A tree is complete if:
Heap structure invariant: �A heap is always a complete tree.
2
7
8
6
9
5
4
helps us avoid degenerate trees
2
7
8
6
5
4
complete
not complete
NBIT209/DIFT204
13
Binary Heap invariants summary
One flavor of heap is a binary heap.
8
9
10
2
4
5
3
6
7
1
22
36
47
2
4
8
9
10
3
1
5
This is a big idea! (heap invariants!)
NBIT209/DIFT204
14
Self Check - Are these valid heaps?
Binary Heap Invariants:
2
3
5
7
8
4
9
11
10
7
9
8
5
6
4
3
7
1
6
INVALID
INVALID
VALID
NBIT209/DIFT204
15
Heap heights
A binary heap bounds our height at Theta(log(n)) because it’s complete – and it’s actually a little stricter and better than AVL.
4
5
8
7
10
2
9
11
13
This means the runtime to traverse from root to leaf or leaf to root will be log(n) time.
NBIT209/DIFT204
16
Priority Queue ADT
Priority Queue possible implementations
Heap invariants
Heap height
Questions?
NBIT209/DIFT204
17
Priority Queue ADT
Binary Heap
Binary Heap Methods
NBIT209/DIFT204
18
Implementing peekMin()
4
5
8
7
10
2
9
11
13
NBIT209/DIFT204
19
Implementing removeMin()
4
5
8
7
10
2
9
11
13
Runtime:
Locating min = O(1)
Fixing heap = ?
4
5
8
7
10
13
9
11
Structure invariant restored
Heap invariant broken
1. Return min
2. Replace with bottom level right-most node
NBIT209/DIFT204
20
Implementing removeMin() - percolateDown
Runtime:
Locating min = O(1)
Fixing heap = ?
4
5
8
7
10
13
9
11
.4.
13
.5.
13
13
11
Structure invariant restored
Heap invariant restored
What’s the worst-case running time?
Have to:
(how many times do we have to swap?)
This is why we want to keep the height of the tree small! The height of these tree structures (BST, AVL, heaps) directly correlates with the worst case runtimes
This is a big idea! (height of all these tree DS correlates w worst case runtimes – we want to design our trees to have reasonably small height!)
1. Return min
2. Replace with bottom level right-most node
3. percolateDown()
Recursively swap parent with smallest child until
parent is smaller than both children
(or we’re at a leaf).
NBIT209/DIFT204
21
Practice: removeMin()
10
17
14
9
11
5
13
20
22
16
15
24
19
18
18
18
9
18
11
1.) Remove min node
2.) replace with bottom level right-most node
3.) percolateDown - Recursively swap parent with smallest child
until parent is smaller than both children
(or we’re at a leaf).
NBIT209/DIFT204
22
percolateDown()
Why does percolateDown swap with the smallest child instead of just any child?
4
5
8
7
10
13
9
11
If we swap 13 and 7, the heap invariant isn’t restored!
7 is greater than 4 (it’s not the smallest child!) so it will violate the invariant.
NBIT209/DIFT204
23
Implementing add()
add() Algorithm:
i.e. swap with parent, until your parent
is smaller than you (or you’re the root).
4
5
8
7
10
2
9
11
13
3
3
8
3
4
Worst case runtime is similar to removeMin and percolateDown – might have to do log(n) swaps, so the worst-case runtime is Theta(log(n))
NBIT209/DIFT204
24
Practice: Building a minHeap
Construct a Min Binary Heap by adding the following values in this order:
add() Algorithm:
i.e. swap with parent, until your parent is smaller than you (or you’re the root).
10
20
7
15
2
5
percolateUp!
7
10
percolateUp!
2
15
percolateUp!
2
5
Min Binary Heap Invariants
NBIT209/DIFT204
25
minHeap runtimes
removeMin():
add()
Finding the last node/next available spot is the hard part.
You can do it in Θ(log n) time on complete trees, with some extra class variants
But it’s NOT fun
And there’s a much better way (that we’ll talk about Wednesday)!
NBIT209/DIFT204
26
Questions?
NBIT209/DIFT204
27
That’s all!
NBIT209/DIFT204
28