Data Structure Heaps Practice Questions with Solutions

By /

Introductions

A Heap is a special tree-based data structure commonly used to quickly access the largest or smallest value. In a Max Heap, the parent is greater than or equal to its children, while in a Min Heap, the parent is smaller than or equal to its children. These practice questions focus on practical heap operations such as identifying valid heaps, inserting values, removing the root, heapifying, finding the minimum or maximum, and understanding array representation. Data Structure Heaps practice questions with solutions help to understand the concepts.

Question 1: Identify Whether a Tree is a Max Heap

Question

Check whether the following binary tree is a valid Max Heap:

        50
       /  \
      30   40
     / \   / \
    10 20 35 25

Solution

In a Max Heap:

Parent >= Children

Check each parent.

For 50:

50 >= 30 ✓
50 >= 40 ✓

For 30:

30 >= 10 ✓
30 >= 20 ✓

For 40:

40 >= 35 ✓
40 >= 25 ✓

Every parent is greater than or equal to its children.

Output

Valid Max Heap

Answer

Yes, the given tree is a valid Max Heap.

Question 2: Identify Whether a Tree is a Min Heap

Question

Check whether this tree is a valid Min Heap:

        10
       /  \
      20   30
     / \   / \
    40 50 35 60

Solution

In a Min Heap:

Parent <= Children

Check the root:

10 <= 20 ✓
10 <= 30 ✓

Check node 20:

20 <= 40 ✓
20 <= 50 ✓

Check node 30:

30 <= 35 ✓
30 <= 60 ✓

All conditions are satisfied.

Output

Valid Min Heap

Answer

Yes, this is a valid Min Heap.

Question 3: Find the Root of a Max Heap

Question

Find the largest value in this Max Heap:

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

Solution

In a Max Heap, the largest value is always at the root.

The root is:

90

We do not need to search every node.

Output

90

Answer

The largest value is 90.

Question 4: Find the Root of a Min Heap

Question

Find the smallest value in this Min Heap:

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

Solution

In a Min Heap, the smallest value is always at the root.

The root is:

10

Therefore:

Output

10

Answer

The smallest value is 10.

Question 5: Insert a Value into a Max Heap

Question

Insert 60 into this Max Heap:

        50
       /  \
      30   40
     / \
    10 20

Solution

First insert the new value at the next available position:

        50
       /  \
      30   40
     / \   /
    10 20 60

Now compare 60 with its parent 40.

60 > 40

Swap them:

        50
       /  \
      30   60
     / \   /
    10 20 40

Now compare 60 with its new parent 50.

60 > 50

Swap again:

        60
       /  \
      30   50
     / \   /
    10 20 40

Now 60 is at the root, so the Max Heap property is restored.

JavaScript example:

class MaxHeap {
    constructor() {
        this.heap = [];
    }

    insert(value) {

        this.heap.push(value);

        let index = this.heap.length - 1;

        while (index > 0) {

            let parent = Math.floor((index - 1) / 2);

            if (this.heap[parent] >= this.heap[index]) {
                break;
            }

            [this.heap[parent], this.heap[index]] =
            [this.heap[index], this.heap[parent]];

            index = parent;
        }
    }
}

let heap = new MaxHeap();

[50, 30, 40, 10, 20].forEach(value => {
    heap.insert(value);
});

heap.insert(60);

console.log(heap.heap);

Output

[60, 30, 50, 10, 20, 40]

Answer

After inserting 60, the Max Heap becomes:

        60
       /  \
      30   50
     / \   /
    10 20 40

Question 6: Insert a Value into a Min Heap

Question

Insert 5 into this Min Heap:

        10
       /  \
      20   15
     / \
    40 30

Solution

First insert 5 at the next available position:

        10
       /  \
      20   15
     / \   /
    40 30  5

Compare 5 with its parent 15.

5 &lt; 15

Swap:

        10
       /  \
      20    5
     / \   /
    40 30 15

Now compare 5 with its parent 10.

5 &lt; 10

Swap again:

        5
       / \
      20  10
     / \  /
    40 30 15

The Min Heap property is restored.

JavaScript:

class MinHeap {
    constructor() {
        this.heap = [];
    }

    insert(value) {

        this.heap.push(value);

        let index = this.heap.length - 1;

        while (index > 0) {

            let parent = Math.floor((index - 1) / 2);

            if (this.heap[parent] <= this.heap[index]) {
                break;
            }

            [this.heap[parent], this.heap[index]] =
            [this.heap[index], this.heap[parent]];

            index = parent;
        }
    }
}

let heap = new MinHeap();

[10, 20, 15, 40, 30].forEach(value => {
    heap.insert(value);
});

heap.insert(5);

console.log(heap.heap);

Output

[5, 20, 10, 40, 30, 15]

Answer

The new root is 5, and the Min Heap property is restored.

Question 7: Remove the Maximum from a Max Heap

Question

Remove the maximum value from this Max Heap:

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

Solution

In a Max Heap, the maximum value is always the root.

So remove:

90

Move the last element 30 to the root:

        30
       /  \
      70   80
     / \   /
    40 50 60

Now 30 violates the Max Heap property.

Compare it with its children:

70 and 80

The larger child is 80.

Swap 30 and 80:

        80
       /  \
      70   30
     / \   /
    40 50 60

Now compare 30 with its child 60.

60 > 30

Swap:

        80
       /  \
      70   60
     / \   /
    40 50 30

The Max Heap property is restored.

Output

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

Answer

After removing the maximum value, the new Max Heap is:

        80
       /  \
      70   60
     / \   /
    40 50 30

Question 8: Convert an Array into a Max Heap

Question

Convert this array into a Max Heap:

[10, 30, 20, 5, 40]

Solution

Treat the array as a complete binary tree:

        10
       /  \
      30   20
     / \
    5   40

The root 10 is smaller than its children, so the heap property is not satisfied.

After heapifying, the largest value should move toward the root.

One valid Max Heap arrangement is:

        40
       /  \
      30   20
     / \
    5   10

Array representation:

[40, 30, 20, 5, 10]

JavaScript:

function heapifyMax(arr, n, i) {

    let largest = i;

    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest !== i) {

        [arr[i], arr[largest]] =
        [arr[largest], arr[i]];

        heapifyMax(arr, n, largest);
    }
}

function buildMaxHeap(arr) {

    let n = arr.length;

    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapifyMax(arr, n, i);
    }

    return arr;
}

let arr = [10, 30, 20, 5, 40];

console.log(buildMaxHeap(arr));

Output

[40, 30, 20, 5, 10]

Answer

The array after building a Max Heap is:

[40, 30, 20, 5, 10]

Question 9: Find the Parent and Children Using an Array

Question

A Max Heap is stored as:

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

Find the parent and children of the value 70.

Solution

For a zero-indexed heap array:

Parent index = Math.floor((i - 1) / 2)

Left child index = 2 * i + 1

Right child index = 2 * i + 2

The value 70 is at index 1.

Parent index:

Math.floor((1 - 1) / 2)
= 0

So the parent is:

90

Left child index:

2 × 1 + 1 = 3

Value:

40

Right child index:

2 × 1 + 2 = 4

Value:

50

Output

Parent: 90
Left Child: 40
Right Child: 50

Answer

For node 70:

Parent     → 90
Left Child → 40
Right Child → 50

Question 10: Check Whether an Array Represents a Max Heap

Question

Check whether this array represents a valid Max Heap:

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

Solution

For every parent, check whether:

Parent >= Left Child
Parent >= Right Child

Check index 0:

90 >= 70 ✓
90 >= 80 ✓

Check index 1:

70 >= 40 ✓
70 >= 50 ✓

Check index 2:

80 >= 60 ✓
80 >= 30 ✓

All conditions are satisfied.

JavaScript:

function isMaxHeap(arr) {

    let n = arr.length;

    for (let i = 0; i <= Math.floor(n / 2) - 1; i++) {

        let left = 2 * i + 1;
        let right = 2 * i + 2;

        if (left < n && arr[i] < arr[left]) {
            return false;
        }

        if (right < n && arr[i] < arr[right]) {
            return false;
        }
    }

    return true;
}

let arr = [90, 70, 80, 40, 50, 60, 30];

console.log(isMaxHeap(arr));

Output

true

Answer

Yes, [90, 70, 80, 40, 50, 60, 30] represents a valid Max Heap.

Key Takeaways

  • A Heap is a tree-based data structure that is usually represented as an array.
  • A Max Heap keeps the largest value at the root.
  • A Min Heap keeps the smallest value at the root.
  • In a Max Heap, every parent is greater than or equal to its children.
  • In a Min Heap, every parent is smaller than or equal to its children.
  • New values are normally inserted at the next available position and then moved upward using heapify-up.
  • When the root is removed, the last element can replace it and then move downward using heapify-down.
  • In a zero-indexed heap array, the left child of index i is at 2i + 1.
  • The right child is at 2i + 2.
  • The parent of index i is at Math.floor((i - 1) / 2).
  • A heap is a complete binary tree, which means its levels are filled from left to right.
  • Building a heap from an array can be done using the heapify process.
  • Heaps are commonly used in Priority Queues and Heap Sort.
  • A heap is not the same as a Binary Search Tree; a heap only maintains the parent-child priority rule.

FAQs

1. What is a Heap in data structures?

A Heap is a complete binary tree that follows a specific ordering rule between each parent and its children.

2. What is a Max Heap?

A Max Heap is a heap where every parent node has a value greater than or equal to its children. The maximum value is stored at the root.

3. What is a Min Heap?

A Min Heap is a heap where every parent node has a value smaller than or equal to its children. The minimum value is stored at the root.

4. Why is a Heap usually stored in an array?

A heap is a complete binary tree, so its nodes can be stored efficiently in an array without requiring explicit left and right node references.

5. How do you find the left child in a heap array?

For a zero-indexed heap, the left child of a node at index i is located at:

2 × i + 1

6. How do you find the right child in a heap array?

For a zero-indexed heap, the right child of a node at index i is located at:

2 × i + 2

7. What is heapify?

Heapify is the process of rearranging elements so that they satisfy the Max Heap or Min Heap property.

Written by Shubhranshu Shekhar, who has trained 20000+ students in coding.

Related Posts

Scroll to Top