Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Heap Operations
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Let's cover basic operations on heap in this lesson.

1. Find Maximum/Minimum in a Heap

The simplest operation in a heap is retrieving the maximum or minimum element.

  • In a Max Heap, the largest element is always at the root (index 0 in the array representation).
  • In a Min Heap, the smallest element is always at the root (index 0 in the array representation).

Since heaps maintain a complete binary tree structure, accessing the maximum (for max heap) or minimum (for min heap) is a constant-time operation with O(1) complexity.

This operation is useful in priority queues, where we frequently need to fetch the highest or lowest priority element without modifying the structure of the heap.

2. Inserting Elements into a Heap (Heapify Up)

Insertion in a heap always happens at the end of the heap to maintain the complete binary tree structure. However, adding a new element may violate the heap property (Max Heap or Min Heap).

To fix this, we use the Heapify Up (also known as Percolate Up) process. This process compares the newly inserted element with its parent and swaps them if needed, ensuring that the heap property is restored. The element moves up the tree until it reaches the correct position or becomes the root. Since the height of the heap is O(log n), the **insertion operation runs in O(log n) time.

Step-by-step Algorithm for Inserting an Element

  1. Insert the new element at the last position of the heap (end of the array).
  2. Find the parent index using the formula:

\text{parent} = \frac{i - 1}{2}

  1. Compare the element with its parent:
    • If the heap property holds (parent is greater in Max Heap, or smaller in Min Heap), stop.
    • Otherwise, swap the element with its parent.
  2. Move up the tree by setting i = parent and repeat until the root is reached or the heap property is satisfied.

Step-by-Step Example (Min Heap Insertion)

mediaLink

Step 0: Initial State of MinHeap

1 of 8

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  1. Insertion

    • We always insert a new element at the last position in the heap → O(1).
    • Then, we call Heapify Up, which moves the element up the tree.
    • In the worst case, the element moves up to the root, which is O(log n).
    • Total Time Complexity: O(log n).

  2. Heapify Up

    • Compares at most log n elements (height of the heap).
    • Each comparison and swap takes O(1) time.
    • Total Complexity: O(log n).

Space Complexity

  • We use an ArrayList, which stores n elements → O(n).
  • The recursion depth in Heapify Up is at most O(log n).
  • Since we modify the heap in place, the extra space used is O(1).

Note: Similarway, you can insert the element into the max heap.

3. Deleting Elements from a Heap (Heapify Down)

Deletion in a heap always removes the root element (minimum in Min Heap, maximum in Max Heap). However, removing the root breaks the heap structure, so we need to restore the heap property using Heapify Down (also called Percolate Down).

The process is:

  1. Replace the root element with the last element in the heap (to maintain the complete binary tree structure).
  2. Compare the new root with its children and swap it with the smallest child (for Min Heap) or largest child (for Max Heap) if necessary.
  3. Repeat the process down the tree until the heap property is restored.

Step-by-step Algorithm for Deleting the Root (Deletion in Min Heap)

  1. Start from the Root

    • Let i = 0 (starting index of the heap).
    • The root element was replaced with the last element. Now, it may violate the heap property.

  2. Identify Left and Right Children

    • Find the left child of i using the formula: \text{left} = 2i + 1
    • Find the right child of i using the formula: \text{right} = 2i + 2

  3. Find the Smallest Child

    • Compare the left child and right child.
    • If the right child exists and is smaller than the left child, set it as the smallest.
    • Otherwise, the left child is the smallest.

  4. Compare Parent with the Smallest Child

    • If the parent is smaller than or equal to the smallest child, stop (heap property is already valid).
    • If the parent is larger than the smallest child, swap them.

  5. Move Down the Tree

    • Set i = smallestChildIndex (update i to the new position).
    • Repeat steps 2-5 until the element is in the correct position or reaches a leaf node.

  6. End of Algorithm

    • The heap property is restored.

Step-by-Step Example (Min Heap Deletion)

We will delete 13 from the Min Heap in the given example.

Step 1: Initial Min Heap (Before Deletion)

         13
       /    \
     21      16
    /  \    /  \
   24   31 19   68
  /  \   /
 65  26 55

Array Representation: [13, 21, 16, 24, 31, 19, 68, 65, 26, 55]

Step 2: Replace Root (13) with Last Element (55)

         55
       /    \
     21      16
    /  \    /  \
   24   31 19   68
  /  \
 65  26

Array: [55, 21, 16, 24, 31, 19, 68, 65, 26]

  • Now, Heapify Down starts from the root (55).

Step 3: Compare 55 with Its Children (21, 16)

  • Smallest child = 16 (since 16 < 21).
  • 55 > 16, so swap them.

Step 4: Swap 55 with 16

         16
       /    \
     21      55
    /  \    /  \
   24   31 19   68
  /  \
 65  26

Array: [16, 21, 55, 24, 31, 19, 68, 65, 26]

  • Now, Heapify Down continues from index 2 (55).

Step 5: Compare 55 with Its Children (19, 68)

  • Smallest child = 19 (since 19 < 68).
  • 55 > 19, so swap them.

Step 6: Swap 55 with 19

         16
       /    \
     21      19
    /  \    /  \
   24   31 55   68
  /  \
 65  26

Array: [16, 21, 19, 24, 31, 55, 68, 65, 26]

  • Now, Heapify Down stops because 55 is in the correct position.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  1. Deletion

    • Removing the root O(1).
    • Moving the last element to the root O(1).
    • Calling Heapify Down, which moves the element down the tree → O(log n).
    • Total Time Complexity: O(log n).

  2. Heapify Down

    • Compares at most log n elements (height of the heap).
    • Each comparison and swap take O(1) time.
    • Total Complexity: O(log n).

Space Complexity

  • We use an ArrayList, which stores n elements → O(n).
  • The recursion depth in Heapify Down is at most O(log n).
  • Since we modify the heap in place, the extra space used is O(1).

4. Building a Heap from an Unordered Array

When given an unordered array, we can efficiently transform it into a valid heap using the Heapify Down approach. Instead of inserting elements one by one (which takes O(n log n) time), we use the bottom-up heap construction method, which runs in O(n) time.

The process works as follows:

  1. Start from the last non-leaf node and call Heapify Down.
  2. Move upward level by level, ensuring that every subtree satisfies the heap property.
  3. Continue until the root is processed, at which point the array becomes a valid heap.

This method is efficient because it only calls heapifyDown() on half of the elements, and most calls affect only a few levels of the heap.

Algorithm for Building a Heap

  1. Identify the last non-leaf node:

    • Since leaf nodes don’t need heapifying, we start from the last non-leaf node.
    • The last non-leaf node is found at index: \frac{n}{2} - 1
    • This is because leaf nodes start at index n/2 in a 0-based index heap.

  2. Heapify Down each non-leaf node in reverse order:

    • Start from index (n/2 - 1) and move backward to index 0.
    • Call heapifyDown() on each node to ensure the heap property is maintained.

  3. Once the root is heapified, the entire array is now a valid heap.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  1. Heapifying a single node takes O(log n) in the worst case.

  2. We heapify approximately n/2 nodes (only non-leaf nodes).

  3. The total complexity is O(n), derived from the summation of log-depth heapify operations.

    • A heap is a complete binary tree, where half of the nodes are leaf nodes that don’t need heapification.

    • Heapify Down is called only on non-leaf nodes (approximately n/2 nodes).

    • The height of a node determines how far it can move down:

      • Nodes near the bottom move only 1-2 levels.
      • The root node moves at most log n levels.

    • Each Heapify Down operation takes time proportional to its height. The total cost across all nodes is given by:

T(n) = \sum_{i=1}^{\log n} \frac{n}{2^i} \times i

  • Using summation properties, this simplifies to:

T(n) = O(n)

Thus, heap construction runs in O(n) time, making it significantly more efficient than inserting elements one by one.

Space Complexity

  • We use an ArrayList, which stores n elements → O(n).
  • Heapify Down is done in place, so extra space usage is O(1).

✅ Final Space Complexity: O(1) (excluding input storage).

Heap Implementation in Different Programming Languages

Here is how different languages have implemented Heap:

LanguageAPI
C++std::priority_queue
Javajava.util.PriorityQueue
Pythonheapq
JavaScriptN/A
C#System.Collections.Generic.PriorityQueue
Gocontainer/heap

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible