Solution: Convert Max Heap to Min Heap

Let’s solve the Convert Max Heap to Min Heap problem.

We'll cover the following

Statement

Given a list representing a max heap, convert this into a min heap.

Constraints:

  • 00\leq max_heap.length 102\leq 10^2

  • 104-10^4\leq max_heap[i] 104\leq10^4

Solution

In this solution, we convert a given max_heap into a min heap. We achieve this by adjusting the positions of elements within the heap to meet the criteria of a min heap, where each parent node is smaller than its child nodes. This process starts from the halfway point of the heap, typically where the last nonleaf node is found, and iteratively applies the min heap criteria up to the root node.

The adjustment involves comparing each node with its children to identify the smallest among them. We determine the left and right children of a node using the following formulas:

  • left=index2+1\text{left} = \text{index} * 2 + 1

  • right=index2+2\text{right} = \text{index} * 2 + 2

Here are the steps for the comparison:

  • Check whether the node does not have the smallest value among its children.

    • If the value of the left\text{left} child is smaller, then swap the node with the left\text{left} child.

    • Otherwise, swap the node with the right\text{right} child.

  • Apply the above step recursively to ensure the entire subtree rooted at the swapped node satisfies the min heap property.

Continue this process until all the nodes, from the last nonleaf node up to the root, have been checked and adjusted to meet the criteria of a min heap.

Let’s look at the illustration below to better understand the solution:

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.