2. Prerequisite: An Introduction to the Tree Data Structure
Before we can understand the Heap, we must first be familiar with its underlying structure: the Tree. In computer science, a tree is a widely used data structure that simulates a hierarchical structure, with a set of connected nodes.
Core Components
Every tree is composed of a few fundamental components:
-
Node: The primary entity in a tree that contains data. It is also known as a "vertex".
-
Edge: A connection or link between two nodes.
-
Root: The topmost node in a tree. It is the only node that does not have a parent.
Consider the tree structure below:
-
Nodes: {A, B, C, D, E}
-
Edges: {(A-B), (A-C), (B-D), (B-E)}
-
Root: Node A
Hierarchical Terminology
The relationships between nodes in a tree are described using terminology borrowed from family trees:
-
Parent: A node that is directly above another node and connected to it. In our example, A is the parent of B and C.
-
Child: A node that is directly below another node and connected to it. In our example, D and E are children of B.
-
Leaf: A node that has no children. In our example, C, D, and E are leaf nodes.
Structure and Depth
We can measure the structure of a tree in several ways:
-
Level: The level of a node is defined by its distance from the root. The root is at Level 0. Its children are at Level 1, their children are at Level 2, and so on.
-
Depth/Height: The height of a tree is the number of edges on the longest path from the root to a leaf. Our example tree has a height of 2.
Focus on the Binary Tree
While a node in a tree can have any number of children, our focus for understanding heaps will be on a specific type: the Binary Tree.
A Binary Tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
The reason we focus on Binary Trees is that the Heap data structure, which is the engine of Heap Sort, is a specialized type of Binary Tree. Mastering this concept is a fundamental step toward understanding heaps.