The Self-Taught Computer Scientist

2. 
Invert a binary tree using a depth- first traversal.

---

15
Binary Heaps
The rise of Google, the rise of Facebook, the rise of Apple, I think are proof that there is a place for 
computer science as something that solves problems that people face every day.
Eric Schmidt
A priority queue is an abstract data type that describes a data structure where each piece of data has 
a priority. Unlike a queue that releases items on a first- come, first- served basis, a priority queue serves 
elements by priority. It removes the data with the highest priority first, followed by the subsequent 
highest priority data (or the opposite with the smallest value coming first). A heap is one of many 
priority queue implementations. A heap is a tree- based data structure in which each node keeps 
track of two pieces of information: a value and its priority. You call a heap node’s value a key. While 
a node’s key and its priority can be unrelated, if its data is a numerical value, such as an integer or a 
character, you can also use it as its priority. In this chapter, I use the key in the heaps you will see also 
to represent priority.
Computer scientists build heaps using trees. There are many types of heaps (depending on what 
kind of tree you use to create your heap), but you will learn about binary heaps in this chapter.
A binary heap is a heap that you create using a binary tree (Figure 15.1).
There are two types of binary heaps: max heaps and min heaps. A max heap’s 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. For example, Figure 15.2 shows a max heap with the integers 1, 2, 3, 4, 6, 8, and 10.
Figure 15.1: You create a binary heap using a binary tree.

---