The Self-Taught Computer Scientist

15Binary 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).

Figure 15.1 You create a binary heap using a binary tree.

There ...