Heap

Definition

A heap is a tree-based data structure that satisfies the heap property and is usually implemented as a complete binary tree.

In a max heap, every parent node is greater than or equal to its children, so the largest element is at the root.
In a min heap, every parent node is less than or equal to its children, so the smallest element is at the root.

Heaps are commonly stored in arrays because their complete tree structure allows efficient indexing without using explicit pointers.

Main Content

1. Heap Structure and Properties

Complete binary tree structure

: A heap is not just any tree; it is typically a complete binary tree. This means every level of the tree is completely filled except possibly the last level, and nodes in the last level are placed from left to right. This structure makes the heap compact and efficient for array-based storage.

Example of a complete binary tree shape:

Heap property

: The defining rule of a heap is the heap property. In a max heap, each parent is greater than or equal to its children. In a min heap, each parent is less than or equal to its children. This property does not fully sort the tree, but it ensures the root always holds the highest-priority value.

Example of a max heap:

Example of a min heap:

2. Types of Heaps

Max Heap

: In a max heap, the root node stores the maximum value. Every parent node is greater than or equal to its children. This is useful when we need to repeatedly find or remove the largest value, such as in priority-based task selection where higher priority means larger value.

Example:

          100
        /     \
      90       80
     /  \     /  \
    70  60   50  40

Min Heap

: In a min heap, the root node stores the minimum value. Every parent node is less than or equal to its children. This is useful when we need repeated access to the smallest value, such as in event simulation, Dijkstra’s algorithm, or maintaining the smallest deadlines.

Example:

           5
        /     \
      10       15
     /  \     /  \
    20  25   30  35

3. Array Representation and Indexing

Array storage of heaps

: Heaps are often implemented using arrays because the complete tree structure allows efficient mapping of tree nodes to array positions. This avoids the need for linked pointers and makes access faster and simpler.

Index relationships

: For a heap stored in an array:
If a node is at index i
Its left child is at 2i + 1 (for 0-based indexing)
Its right child is at 2i + 2
Its parent is at (i - 1) / 2

Example array for a max heap:

  [90, 70, 80, 40, 50, 60]

This corresponds to:

Why arrays are efficient

: Array representation reduces memory overhead and makes it easy to navigate parent-child relationships using simple index calculations. This is one of the main reasons heaps are practical in implementation.

Working / Process

1. Insertion of a new element

A new element is first inserted at the next available position to keep the tree complete. Then, the heap property is restored using a process called heapify up or sift up. The new element is compared with its parent and swapped upward until the correct position is found.

Example: inserting 85 into a max heap:

After insertion at the next open spot:

           90
         /    \
       70      80
      /  \    /  \
     40  50  60  85

Then it is moved upward until the heap property is satisfied.

2. Deletion of the root element

The root is removed because it contains the highest-priority element. To maintain the complete tree shape, the last element in the heap is moved to the root position. Then the heap property is restored using heapify down or sift down, where the new root is compared with its children and swapped downward if needed.

In a max heap, the larger child is typically selected during heapify down.

3. Heap maintenance (heapify)

Heapify is the process of restoring the heap structure after insertion or deletion.

Heapify up is used after insertion.
Heapify down is used after deletion.

These operations ensure the heap remains valid without sorting the entire data structure. This is why heaps are efficient for priority-based applications.

Advantages / Applications

Efficient priority management

: Heaps are ideal for priority queues because they provide fast access to the highest-priority or lowest-priority element. This makes them useful in operating systems, network scheduling, and event handling systems.

Efficient insertion and deletion

: Insertions and deletions generally take O(log n) time, which is much faster than searching or sorting a full list for every operation. This efficiency is especially valuable when the data changes frequently.

Used in important algorithms

: Heaps are used in many classic algorithms and real-world systems, such as:
Heap sort
Dijkstra’s shortest path algorithm
Prim’s minimum spanning tree algorithm
Task scheduling
Median maintenance systems

Example: In a CPU scheduler, a process with higher priority can be placed at the top of a max heap so it is selected first.

Summary

A heap is a complete binary tree with a special ordering rule.
Max heap keeps the largest value at the root, and min heap keeps the smallest value at the root.
Heaps are commonly stored in arrays and are useful for priority-based operations.
Important terms to remember: heap, max heap, min heap, heapify, sift up, sift down, complete binary tree