The Self-Taught Computer Scientist

priority queue: An abstract data type that describes a data structure where each piece of data has 
a priority.
heap: A tree- based data structure where each node keeps track of two data pieces: the data itself 
and its priority.
key: The value of a node in a heap.
binary heap: A heap that uses a binary tree as its underlying data structure.
max heap: A heap where the parent node’s priority is always greater than or equal to any child 
node’s priority, and the node with the highest priority is the tree’s root.
min heap: A heap where the parent node’s priority is always less than or equal to any child node’s 
priority, and the node with the lowest priority is the root of the tree.
heapifying: Creating a heap from a data structure like an array.
balancing a heap: Reordering keys that are out of order.
Challenge
1. 
Write a function that can accept a binary tree as a parameter and return 
True
if it is a min heap 
and 
False
if not.

---

---

16
Graphs
Learning to code will be a huge booster for your future, no matter what your professional 
plans may be. Learning to code will also make you extremely cool!
Max Levchin
A graph is an abstract data type in which a piece of data connects to one or more other pieces 
of data. Each piece of data in a graph is called a vertex or a 
node. A vertex has a name called a key.
A vertex can have additional data called its payload. The connection between vertices in a graph is 
called an edge. A graph’s edges can contain a weight: the cost to travel between vertices. For example, 
if you created a graph representing the data in a map, each vertex could be a city, and the weight bet-
ween two vertices could be the distance between them (Figure 16.1).
There are several types of graphs, including directed graphs, undirected graphs, and complete 
graphs. A directed graph is one in which each edge has a direction associated with it, and you can 
move between two vertices only in that direction. The connection between two vertices is typically in 
Palo Alto
San
Francisco
63.4°F
Oakland
10
Weight
Edge
Vertex
Key
44
43
24
Pleasanton
Payload