Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Interview prep > Heap > Flashcards

Heap Flashcards

1
Q

What is heap ?

A

A Heap is a Tree-based data structure, which satisfies the below properties:

1- A Heap is a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible).

2- A Heap is either Min Heap or Max Heap. In a Min-Heap, the key at root must be minimum among all keys present in the Binary Heap. The same property must be recursively true for all nodes in the Tree. Max Heap is similar to MinHeap.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is binary heap ?

A

A Binary Heap is a heap where each node can have at most two children. In other words, a Binary Heap is a complete Binary Tree satisfying the above-mentioned properties.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what is min heap. Explain with example

A

A min-heap is a binary heap data structure where the value of the root node is always the smallest among all nodes. It satisfies the heap property:

  • For every node ( i ):
    • ( A[i] \leq A[2i + 1] ) (left child)
    • ( A[i] \leq A[2i + 2] ) (right child)

This property ensures that the smallest element is always at the root of the tree, which allows for efficient retrieval.

Characteristics of Min-Heap:
1. Binary Tree Representation: It is usually implemented using arrays, where:
- Parent index: ( i )
- Left child index: ( 2i + 1 )
- Right child index: ( 2i + 2 )
2. Complete Binary Tree: All levels are filled except possibly the last, which is filled from left to right.

Operations:
- Insertion: Add the element to the end and “heapify up” to maintain the min-heap property.
- Deletion (Min-Element): Replace the root with the last element, remove it, and “heapify down.”
- Peek Minimum: Always ( O(1) ), as the root contains the smallest element.

Example:
Consider the array: ([3, 5, 9, 6, 8, 20, 10, 12, 18, 9])

Min-Heap Construction:
After inserting elements step-by-step and applying the heap property, the resulting min-heap is:

        3
      /   \
     5     9
    / \   / \
   6   8 20  10
  / \
 12 18

Array Representation:
The heap can also be represented as an array:
[ 3, 5, 9, 6, 8, 20, 10, 12, 18, 9 ]

Example Operations:
1. Insert 2:
- Add 2 at the end.
- “Heapify up” → Swap 2 with 6, then 2 with 3.
- Resulting heap: [ 2, 5, 3, 6, 8, 20, 10, 12, 18, 9 ].

  1. Delete Min:
    • Remove 3 (root), replace it with 9.
    • “Heapify down” → Swap 9 with 5.
    • Resulting heap: [ 5, 6, 9, 12, 8, 20, 10, 9, 18 ].

Applications:
- Priority Queues: Efficient retrieval of the smallest element.
- Heap Sort: Sorting elements in ( O(n \log n) ).
- Graph Algorithms: Prim’s and Dijkstra’s algorithms.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Example of max heap ?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

How to represent binary heap ?

A

Since a Binary Heap is a complete Binary Tree, it can be easily represented using Arrays.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

what is the index of root of binary heap is ?

A

0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

which index returns the parent of the heap

A

Arr[(i-1)/2] Returns the parent node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

which index returns the left child node ?

A

Arr[(2*i)+1] Returns the left child node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

which index returns the right child node ?

A

Arr[(2*i)+2] Returns the right child node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How to get the max element in a max heap. approach only

A

Getting Maximum Element: In a Max-Heap, the maximum element is always present at the root node which is the first element in the array used to represent the Heap. So, the maximum element from a max heap can be simply obtained by returning the root node as Arr[0] in O(1) time complexity.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How to get the min element in a min heap. approach only

A

Getting Minimum Element: In a Min-Heap, the minimum element is always present at the root node which is the first element in the array used to represent the Heap. So, the minimum element from a minheap can be simply obtained by returning the root node as Arr[0] in O(1) time complexity.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

what do you mean by Heapifying an Element

A

Generally, on inserting a new element onto a Heap, it does not satisfy the property of Heap as stated above on its own. The process of placing the element at the correct location so that it satisfies the Heap property is known as Heapify.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How to heapify a heap into a max heap ? approach only

A

Heapifying in a Max Heap: The property of Max Heap says that every node’s value must be greater than the values of its children nodes. So, to heapify a particular node swap the value of the node with the maximum value of its children nodes and continue the process until all of the nodes below it satisfies the Heap property.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the time complexity to heapify a tree ?

A

Time Complexity: The time complexity to heapify a single node is O(h), where h is equal to log(N) in a complete binary tree where N is the total number of nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is extract min in min heap ?

A

it means deleting or returning the root of the tree in a min heap

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Algorithm for Root Deletion (Or Extract Min in Min Heap):

A

Since deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted by the last element and delete the last element of the Heap.
Replace the root or element to be deleted by the last element.
Delete the last element from the Heap.
Since, the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of root.

17
Q

Implementation of root deletion in a min heap

A

include

Since deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted by the last element and delete the last element of the Heap.
Replace the root or element to be deleted by the last element.
Delete the last element from the Heap.
Since, the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of root.

// C++ program for implement deletion in Heaps

using namespace std;

// To heapify a subtree rooted with node i which is
// an index in arr[]. N is size of heap
void heapify(int arr[], int n, int i)
{
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2
    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;
    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}
// Function to delete the root from Heap
void deleteRoot(int arr[], int& n)
{
    // Get the last element
    int lastElement = arr[n - 1];
    // Replace root with first element
    arr[0] = lastElement;
    // Decrease size of heap by 1
    n = n - 1;
    // heapify the root node
    heapify(arr, n, 0);
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}
// Driver Code
int main()
{
    // Array representation of Max-Heap
    //     10
    //    /  \
    //   5    3
    //  / \
    // 2   4
    int arr[] = { 10, 5, 3, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);

deleteRoot(arr, n);

printArray(arr, n);

return 0; }

Output:
5 4 3 2

18
Q

Implementation of root deletion in a min heap

Write the code for the initialization of largest, left and right variables

A

int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2i + 1
int r = 2 * i + 2; // right = 2i + 2

19
Q

Implementation of root deletion in a min heap

Write the code If left child is larger than root

A

if (l < n && arr[l] > arr[largest])

largest = l;

20
Q

Implementation of root deletion in a min heap

Write the code If right child is larger than largest so far

A

if (r < n && arr[r] > arr[largest])

largest = r;

21
Q

Implementation of root deletion in a min heap

Write code If largest is not root

A

if (largest != i) {
swap(arr[i], arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
22
Q

Write the Function to delete the root from Heap

A 
void deleteRoot(int arr[], int& n)
{
    // Get the last element
    int lastElement = arr[n - 1];
    // Replace root with first element
    arr[0] = lastElement;
    // Decrease size of heap by 1
    n = n - 1;
    // heapify the root node
    heapify(arr, n, 0);
}
23
Q

How to insert in a heap ? approach only.

A

Process of Insertion: Elements can be isnerted to the heap following a similar approach as discussed above for deletion. The idea is to:
First increase the heap size by 1, so that it can store the new element.
Insert the new element at the end of the Heap.
This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap, heapify this newly inserted element following a bottom-up approach.

24
Q

Implementation of insertion of a element in a heap

A

define MAX 1000 // Max size of Heap

Process of Insertion: Elements can be isnerted to the heap following a similar approach as discussed above for deletion. The idea is to:
First increase the heap size by 1, so that it can store the new element.
Insert the new element at the end of the Heap.
This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap, heapify this newly inserted element following a bottom-up approach.

// C++ program to insert new element to Heap

#include 
using namespace std;
// Function to heapify ith node in a Heap
// of size n following a Bottom-up approach
void heapify(int arr[], int n, int i)
{
    // Find parent
    int parent = (i - 1) / 2;
if (parent >= 0) {
        // For Max-Heap
        // If current node is greater than its parent
        // Swap both of them and call heapify again
        // for the parent
        if (arr[i] > arr[parent]) {
            swap(arr[i], arr[parent]);
            // Recursively heapify the parent node
            heapify(arr, n, parent);
        }
    }
}
// Function to insert a new node to the Heap
void insertNode(int arr[], int& n, int Key)
{
    // Increase the size of Heap by 1
    n = n + 1;
    // Insert the element at end of Heap
    arr[n - 1] = Key;
    // Heapify the new node following a
    // Bottom-up approach
    heapify(arr, n, n - 1);
}
// A utility function to print array of size n
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
cout << "\n"; }
// Driver Code
int main()
{
    // Array representation of Max-Heap
    //     10
    //    /  \
    //   5    3
    //  / \
    // 2   4
    int arr[MAX] = { 10, 5, 3, 2, 4 };
int n = 5;

int key = 15;

insertNode(arr, n, key);
    printArray(arr, n);
    // Final Heap will be:
    //     15
    //    /   \
    //   5     10
    //  / \   /
    // 2   4 3
    return 0;
}
25
Q

Implementation of insertion of a element in a heap

How to find the index of the parent node ?

A 
// Find parent
    int parent = (i - 1) / 2;
26
Q

Implementation of insertion of a element in a heap

Write a Function to heapify ith node in a Heap of size n following a Bottom-up approach

A 
void heapify(int arr[], int n, int i)
{
    // Find parent
    int parent = (i - 1) / 2;
if (parent >= 0) {
        // For Max-Heap
        // If current node is greater than its parent
        // Swap both of them and call heapify again
        // for the parent
        if (arr[i] > arr[parent]) {
            swap(arr[i], arr[parent]);
            // Recursively heapify the parent node
            heapify(arr, n, parent);
        }
    }
}
27
Q

Implementation of insertion of a element in a heap

Write the function to insert a node in a heap

A 
void insertNode(int arr[], int& n, int Key)
{
    // Increase the size of Heap by 1
    n = n + 1;
    // Insert the element at end of Heap
    arr[n - 1] = Key;
    // Heapify the new node following a
    // Bottom-up approach
    heapify(arr, n, n - 1);
}
28
Q

A 3-ary max heap is like a binary max heap, but instead of 2 children, nodes have 3 children. A 3-ary heap can be represented by an array as follows: The root is stored in the first location, a[0], nodes in the next level, from left to right, is stored from a[1] to a[3]. The nodes from the second level of the tree from left to right are stored from a[4] location onward. An item x can be inserted into a 3-ary heap containing n items by placing x in the location a[n] and pushing it up the tree to satisfy the heap property.

Which one of the following is a valid sequence of elements in an array representing 3-ary max heap?
(A) 1, 3, 5, 6, 8, 9
(B) 9, 6, 3, 1, 8, 5
(C) 9, 3, 6, 8, 5, 1
(D) 9, 5, 6, 8, 3, 1
A

Answer: (D)

Explanation: Following 3-ary Max Heap can be constructed from sequence given option (D)

29
Q

Suppose the elements 7, 2, 10 and 4 are inserted, in that order, into the valid 3- ary max heap found in the above question(9, 5, 6, 8, 3, 1), Which one of the following is the sequence of items in the array representing the resultant heap?

(A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(B) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(C) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

A

A

30
Q

Consider a binary max-heap implemented using an array. Which one of the following array represents a binary max-heap?

(A) 25,12,16,13,10,8,14
(B) 25,14,13,16,10,8,12
(C) 25,14,16,13,10,8,12
(D) 25,14,12,13,10,8,16

A

Answer (C)

A tree is max-heap if data at every node in the tree is greater than or equal to it’s children’ s data.

In array representation of heap tree, a node at index i has its left child at index 2i + 1 and right child at index 2i + 2.

31
Q 
What is the content of the array after two delete operations on the correct answer to the previous question(25,14,16,13,10,8,12) ? 
(A) 14,13,12,10,8
(B) 14,12,13,8,10
(C) 14,13,8,12,10
(D) 14,13,12,8,10
A

Answer(D)

For Heap trees, deletion of a node includes following two operations.

1) Replace the root with last element on the last level.
2) Starting from root, heapify the complete tree from top to bottom..

32
Q 
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is
(A) theta(logn)
(B) theta(n)
(C) theta(nlogn)
(D) theta(n^2)
A

We can reduce the problem to Build Heap for 2n elements. Time taken for build heap is O(n)

33
Q 
In a binary max heap containing n numbers, the smallest element can be found in time (GATE CS 2006)
(A) 0(n)
(B) O(logn)
(C) 0(loglogn)
(D) 0(1)
A

Answer (A)
In a max heap, the smallest element is always present at a leaf node. So we need to check for all leaf nodes for the minimum value. Worst case complexity will be O(n)

34
Q

The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a Max Heap. The resultant Max Heap is.

A
35
Q 
Given two max heaps of size n each, what is the minimum possible time complexity to make a one max-heap of size from elements of two max heaps?
(A) O(nLogn)
(B) O(nLogLogn)
(C) O(n)
(D) O(nLogn)
A

Answer: (C)

Explanation: We can build a heap of 2n elements in O(n) time. Following are the steps.

Create an array of size 2n and copy elements of both heaps to this array.

Call build heap for the array of size 2n. Build heap operation takes O(n) time.

36
Q

Which of the following Binary Min Heap operation has the highest time complexity?
(A) Inserting an item under the assumption that the heap has capacity to accommodate one more item
(B) Merging with another heap under the assumption that the heap has capacity to accommodate items of other heap
(C) Deleting an item from heap
(D) Decreasing value of a key

A

Answer: (B)

Explanation: The merge operation takes O(n) time, all other operations given in question take O(Logn) time.

The Binomial and Fibonacci Heaps do merge in better time complexity.

Interview prep (23 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions