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.