COMP 210: Data Structures

The Heap: A Specialized Binary Tree

Introduction and Definition

The Heap is a specialized tree-based data structure that is designed to quickly access the largest (or smallest) element in a collection. It is the most common and efficient way to implement a Priority Queue.

A data structure qualifies as a Heap if it meets two fundamental properties:

1. Structural Property: Complete Binary Tree

   A heap must be a complete binary tree. This means two things:

   1. Every level of the tree, except possibly the last, is completely filled.

   2. The nodes on the last level must be filled from left to right.

   This strict structural requirement is key because it guarantees the tree is always balanced. (It also allows for a highly efficient implementation using a simple array – See Implementing a Complete Binary Tree as an Array.)

2. Heap Property: Ordering Invariant

   The heap property defines the relationship between a parent node and its children. There are two types of heaps:

   • Max Heap: For every node in the tree, the value of the node must be greater than or equal to the values of its children. The largest element in the entire structure is always at the root.

   • Min Heap: For every node in the tree, the value of the node must be less than or equal to the values of its children. The smallest element in the entire structure is always at the root.

Core Operations and Complexity

The efficiency of a heap comes from its ability to restore the Heap Property (Max or Min) very quickly after an insertion or deletion. This process is often called “Heapifying” or “Percolating.”

Insertion (O(log N))

1. Placement: The new element is always placed at the next available spot in the array (the end), maintaining the structural property.

2. Heapify – Percolate Up: If the new element violates the Heap Property (e.g., in a Max Heap, the child is larger than its parent), the element is repeatedly swapped with its parent until the property is restored or the root is reached. The maximum number of swaps is equal to the height of the tree, which is log₂N.

Deletion/Extraction (O(log N))

Deletion is almost always the removal of the root node (the maximum element in a Max Heap, or the minimum in a Min Heap).

1. Removal & Replacement: The root element is extracted and saved. The hole left at the root is filled by the element from the last node in the array (to maintain the structural property).

2. Heapify – Percolate Down: The replacement element at the root is likely to violate the Heap Property. It is repeatedly swapped down with the larger of its two children (in a Max Heap) until the property is restored. Since the element moves down the height of the tree, this operation is also O(log N).