Heap Tree in Data Structure

A Heap Tree is a specialized binary tree used primarily for priority queue operations. It follows two key properties:

  1. Heap Order Property

    • Max-Heap: The parent node is always greater than or equal to its children.
    • Min-Heap: The parent node is always smaller than or equal to its children.

  2. Complete Binary Tree Property

    • A heap is always a complete binary tree, meaning all levels are fully filled except possibly the last level, which is filled from left to right.

Examples of Max-Heap

Example 01: Max-Heap with 2 Elements

Elements inserted: 10, 5

The Max heap structure is given in the following diagram

Max-Heap Tree - Example 01.

In the correct Max-heap tree, both conditions are satisfied

  • First, Each parent is greater than its children
  • second, It is a complete binary tree.

Example 02: Max-Heap with 9 Elements

Elements inserted: 35,25,30,15,20,5,10,1,2

The Max heap structure is given in the following diagram

Max-Heap Tree - Example 02

In the correctly marked Max-Heap tree, both conditions are satisfied

  • First, each parent node is greater than its children. Second, it is a complete binary tree.

Examples of Min – Heap

Example 01: Min-Heap with 2 Elements

Elements inserted: 5, 10

The min-heap structure is given in the following diagram

Min-Heap Tree - Example 01

In the correct Min-heap tree, both conditions are satisfied

  • First, Each parent is less than its children
  • second, It is a complete binary tree.

Example 02: Min-Heap with 9 Elements

Elements inserted: 5,10,15,20,15,20,25,30,35

The Min heap structure is given in the following diagram

Min-Heap Tree - Example 02

In the correctly marked Min-Heap tree, both conditions are satisfied

  • First, each parent node is less than its children. Second, it is a complete binary tree.

Max Heap to Array Representation

A heap is conceptually a binary tree, but it is implemented using an array. This makes heap operations (insertion, deletion, and heapify) efficient without using extra pointers like in a linked tree. The following diagram explains it

Max-Heap Tree to Array Representation

Insertion in Heap Tree (Heapify Up)

in Heap Trees, log N and log₂ N are the same

Steps to Insert a New Element into a Max-Heap:

  1. Increase the heap size by 1 (to accommodate the new element).
  2. Insert the new element at the last position (end of the array).
  3. Perform Up-Heap (Heapify-Up) operation:
    • Compare the new element with its parent.
    • If the new element is greater than the parent, swap them.
    • Repeat this process until the Max-Heap property is restored (or the element reaches the root).

Example: 80,60,70,50,40,30,20 are elements of Heap Tree initially. Let insert 90 in given heap tree by using above steps.

Insertion in MAX heap tree with example

Deletion in Heap Tree (Heapify Down)

We always delete the root node in a heap because it preserves heap properties, ensures efficiency, and maintains structure. Deleting the root is efficient because

  • Replace the root with the last element (O(1) operation).
  • Perform Heapify-Down (O(log N)), which is fast.

What If We Want to Delete a Specific Node?

  • Possible but inefficient!
  • We would need to find the node (O(N)), replace it, and then Heapify-Up (O(log N)) or Heapify-Down.

Important: Instead, a priority queue is a better choice if we need flexible deletions.

Steps for Deletion in a Max-Heap:

  1. Remove the root node (max element).
  2. Replace the root with the last element in the heap.
  3. Reduce the heap size by 1.
  4. Perform Down-Heap (Heapify-Down) operation:
    • Compare the new root with its largest child.
    • If the new root is smaller than the largest child, swap them.
    • Repeat this process until the Max-Heap property is restored.

Example (Max-Heap): A Max-heap tree with elements of 80,60,70,50,40,30,20. We need to delete root node 80. The mechanism is given in the following diagram.

Deletion in Heap Tree

deletion in heap time complexity is given below

  • Worst-case: O(log N) (because we swap down through the height of the tree).
  • Best-case: O(1) (if no swaps are needed)

Heap Operations

  1. Insertion – Add a new node at the end and adjust it upward (Heapify Up).
  2. Deletion (Extract Max/Min) – Remove the root and restructure the heap (Heapify Down).
  3. Heapify – Convert an unsorted array into a heap.
  4. Heap Sort – A sorting algorithm using the heap data structure.

Applications of Heap

  • Priority Queues (Dijkstra’s Algorithm, CPU Scheduling)
  • Heap Sort (Efficient sorting method)
  • Graph Algorithms (Prim’s and Dijkstra’s Algorithm)
  • Finding Kth Largest/Smallest Element