Trees, Heaps, and Priority Queues

This chapter groups together three important data structures: trees, heaps, and priority queues. Trees are our first example of a nonlinear structure for containing objects. Although conceptually more complex than linear data structures, trees offer the opportunity for improved efficiency in operations such as inserting, removing, and searching for contained objects. Heaps are also nonlinear in structure and contained objects must be organized in agreement with an order relationship between each node and its descendants. A heap may be efficiently implemented using a binary tree. A priority queue is a special kind of queue that contains prioritized objects (usually based on a key) in a way that the objects are removed based on their priority (highest priority first). Priority queues may be implemented using a heap. There is a nonessential but beneficial relationship among these three data structures; that is why they are grouped together in this chapter. Additional variations on binary trees are covered in later chapters. Trees A tree is a nonlinear data structure that derives its name from a similarity between its defining terminology and our friends in the forest, real trees. A tree data structure is considerably more constrained in its variety than a real tree and is typically viewed upside down, with its root at the top and leaves on the bottom. A tree is usually accessed from its root , then down through its branches to the leaves.