1
This lecture introduces heaps, which are used in the Priority Queue
project of Chapter 11. The lecture includes the algorithms for adding to
❐Chapter 11 has several
programming projects, including a
Heaps
Data Structures
and Other Objects
Using C++
2
A heap is a data structure with several applications, including a way to
Heaps
3
Heaps
A heap is a
certain kind of
Root
4
Heaps
Left child
The second node is
5
Heaps
Complete
binary tree.
Right child
of the
root
6
Heaps
Complete
binary tree.
7
Heaps
Complete
binary tree.
8
Heaps
Complete
binary tree.
9
Heaps
Complete
binary tree.
10
Heaps
Complete
binary tree.
11
Heaps
A heap is a
certain kind
of complete
binary tree.
4222127
23
45
35
12
This is a handy property because the biggest node is always at the top.
Heaps
A heap is a
certain kind
of complete
binary tree.
The “heap property”
requires that each
19
4222127
23
45
35
13
We can add new elements to a heap whenever we like. Because the
Of course, we now have a problem: The heap property is no longer
valid. The 42 is bigger than its parent 27.
Adding a Node to a Heap
❶Put the new node in the
next available spot.
❷Push the new node
upward, swapping with
its parent until the new
node reaches an
acceptable location. 19
4222127
23
45
35
42
14
Adding a Node to a Heap
❶Put the new node in the
next available spot.
❷Push the new node
upward, swapping with
its parent until the new
node reaches an
acceptable location. 19
4222142
23
45
35
27
15
Adding a Node to a Heap
❶Put the new node in the
next available spot.
❷Push the new node
upward, swapping with
its parent until the new
node reaches an
acceptable location. 19
4222135
23
45
42
27
16
Adding a Node to a Heap
✔The parent has a key
that is >= new node, or
✔The node reaches the
23
45
42