A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Heaps

Heaps are of several different types, but we’re going to focus on the binary heap.

The binary heap is a specific kind of binary tree. As a reminder, a binary tree is a tree where each node has a maximum of two child nodes. (The binary search tree from the last chapter was one specific type of binary tree.)

Now, even binary heaps come in two flavors: the max-heap and the min-heap. We’re going to work with the max-heap for now, but as you’ll see later, the difference between the two is trivial.

Going forward, I’m going to refer to this data structure simply as a heap, even though we’re specifically working with a binary max-heap.

The heap is a binary tree that maintains the following conditions:

• The value of each node must be greater ...