Python Data Structures and Algorithms

Heaps

At this point, we shall briefly introduce the heap data structure. A heap is a specialization of a tree in which the nodes are ordered in a specific way. Heaps are divided into max and min heaps. In a max heap, each parent node must always be greater than or equal to its children. It follows that the root node must be the greatest value in the tree. A min heap is the opposite. Each parent node must be less than or equal to both its children. As a consequence, the root node holds the lowest value.

Heaps are used for a number of different things. For one, they are used to implement priority queues. There is also a very efficient sorting algorithm, called heap sort, that uses heaps. We are going to study these in depth in subsequent chapters. ...