Heap Data Structure Properties

Managing elements based on their priority is fundamental to many optimization tasks. A Heap is a specialized tree-based data structure specifically designed to efficiently handle these priority-based operations. While various types of heaps exist, we will primarily focus on the Binary Heap, which is the most common implementation.

Binary heaps adhere to two main properties that ensure their efficiency: the Heap Property and the Structural Property.

The Heap Property: Ordering Elements

The core idea behind a heap is the specific ordering relationship it maintains between parent and child nodes. This relationship defines whether the heap keeps track of the smallest or largest element at the top. There are two types:

Min-Heap

In a Min-Heap, the value of each parent node is less than or equal to the values of its children. This property recursively holds true for all nodes in the tree. Consequently, the smallest element in the entire collection is always located at the root node.

A simple Min-Heap. Note that the root (10) is the smallest value, and every parent is smaller than or equal to its children (e.g., 15 <= 40, 15 <= 50).

Max-Heap

Conversely, in a Max-Heap, the value of each parent node is greater than or equal to the values of its children. This ensures that the largest element in the collection always resides at the root node.

A simple Max-Heap. The root (100) is the largest value, and every parent is greater than or equal to its children (e.g., 50 >= 15, 50 >= 40).

This heap property is important to providing fast access to the minimum (in a Min-Heap) or maximum (in a Max-Heap) element.

The Structural Property: Complete Binary Tree

The second property relates to the shape of the tree. A binary heap is always maintained as a Complete Binary Tree. This means:

1. All levels of the tree are completely filled, except possibly the lowest level.
2. If the lowest level is not full, the nodes in that level are filled from left to right without any gaps.

A Complete Binary Tree. All levels are full except the last, which is filled from left to right (nodes H and I).

Why is this structural property important? It allows a binary heap to be stored very efficiently using a simple array or list. The relationships between parent and child nodes can be calculated directly from their indices in the array, eliminating the need for explicit pointers.

For a node at index $i$ in a zero-based array:

• Its left child is at index $2i + 1$.
• Its right child is at index $2i + 2$.
• Its parent is at index $\lfloor (i - 1) / 2 \rfloor$.

This array representation is compact and cache-friendly. The diagram below shows the Max-Heap from before mapped to an array representation:

The Max-Heap structure mapped to its corresponding array representation. The elements fill the array level by level, left to right.

These two properties, the heap property (min or max ordering) and the structural property (complete binary tree allowing array representation), are fundamental. They enable heaps to serve as efficient backbones for Priority Queues and facilitate operations like insertion and extraction in logarithmic time, specifically $O(\log n)$, where $n$ is the number of elements in the heap. We will explore these operations in the next section.