Min Heap vs Max Heap When to Use Which in DSA Javascript - Build Both Approaches

Min Heap vs Max Heap: When to Use Which

📖 Scenario: Imagine you are organizing a game tournament. You want to keep track of players' scores to quickly find the player with the lowest score and the player with the highest score at any time.

🎯 Goal: You will build two simple heaps: a Min Heap to find the player with the lowest score quickly, and a Max Heap to find the player with the highest score quickly. This will help you understand when to use each heap type.

📋 What You'll Learn

Create an array called scores with exact player scores

Create a variable called minHeap to store the minimum scores

Create a variable called maxHeap to store the maximum scores

Use JavaScript array methods to build the heaps

Print the minimum and maximum scores from the heaps

💡 Why This Matters

🌍 Real World

Heaps are used in games, scheduling tasks, and managing priorities where you need quick access to smallest or largest items.

💼 Career

Understanding heaps is important for software engineers working on performance-critical applications, data processing, and algorithms.

1

Create the player scores array

Create an array called scores with these exact values: 15, 22, 8, 19, 31, 5, 27.

DSA Javascript

// Create the scores array with the exact values
// Your code here

Hint

Use square brackets [] to create an array and separate numbers with commas.

2

Create minHeap and maxHeap variables

Create two variables: minHeap and maxHeap. Initialize both as empty arrays.

DSA Javascript

const scores = [15, 22, 8, 19, 31, 5, 27];
// Create minHeap and maxHeap as empty arrays
// Your code here

Hint

Use [] to create empty arrays and let to declare variables.

3

Build the minHeap and maxHeap arrays

Use the scores array to fill minHeap with scores sorted from smallest to largest, and maxHeap with scores sorted from largest to smallest. Use the slice() method to copy the array and the sort() method with appropriate compare functions.

DSA Javascript

const scores = [15, 22, 8, 19, 31, 5, 27];
let minHeap = [];
let maxHeap = [];
// Fill minHeap with scores sorted ascending
// Fill maxHeap with scores sorted descending
// Your code here

Hint

Use slice() to copy the array before sorting to avoid changing the original.

For ascending sort, use (a, b) => a - b. For descending, use (a, b) => b - a.

4

Print the minimum and maximum scores

Print the smallest score from minHeap and the largest score from maxHeap using console.log. Access the first element of each array.

DSA Javascript

const scores = [15, 22, 8, 19, 31, 5, 27];
let minHeap = scores.slice().sort((a, b) => a - b);
let maxHeap = scores.slice().sort((a, b) => b - a);
// Print the smallest score from minHeap
// Print the largest score from maxHeap
// Your code here

Hint

The smallest score is the first element of minHeap. The largest score is the first element of maxHeap.

Practice

1. Which heap type is best suited when you need to quickly find the smallest element in a collection?

easy

A. Binary Search Tree

B. Min Heap

C. Max Heap

D. Hash Table

Solution

1. Step 1: Understand the heap types

   A Min Heap always keeps the smallest element at the root, making it easy to access.

2. Step 2: Match the requirement with heap property

   Since we want quick access to the smallest element, Min Heap is the best choice.

3. Final Answer:

   Min Heap -> Option B

4. Quick Check:

   Smallest element = Min Heap [OK]

Hint: Smallest element? Use Min Heap [OK]

Common Mistakes:

• Confusing Min Heap with Max Heap
• Choosing data structures unrelated to heaps
• Thinking Max Heap gives smallest element

2. Which of the following is the correct way to insert an element into a Max Heap in JavaScript?

easy

A. Add element at the end and heapify down

B. Add element at root and heapify down

C. Add element at the end and heapify up

D. Add element at root and heapify up

Solution

1. Step 1: Recall Max Heap insertion process

   New elements are added at the end (bottom level) to maintain complete tree property.

2. Step 2: Restore heap property by heapifying up

   After insertion, heapify up swaps the new element with parents if larger, to maintain Max Heap.

3. Final Answer:

   Add element at the end and heapify up -> Option C

4. Quick Check:

   Insert = end + heapify up [OK]

Hint: Insert at end, then heapify up for Max Heap [OK]

Common Mistakes:

• Heapifying down after insertion
• Inserting at root directly
• Confusing heapify direction

3. Consider the following JavaScript code using a Min Heap implementation:

const minHeap = new MinHeap();
minHeap.insert(10);
minHeap.insert(5);
minHeap.insert(20);
minHeap.insert(3);
console.log(minHeap.extract());

What will be printed?

medium

A. 20

B. 10

C. 5

D. 3

Solution

1. Step 1: Insert elements into Min Heap

   Elements 10, 5, 20, 3 are inserted. Min Heap keeps smallest element at root.

2. Step 2: Extract removes and returns the smallest element

   Extract returns the root, which is the smallest: 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Min Heap extract = smallest element [OK]

Hint: Extract from Min Heap returns smallest [OK]

Common Mistakes:

• Thinking extract returns largest
• Confusing Min Heap with Max Heap
• Ignoring heap property after insertions

4. You have a Max Heap implementation but notice that after inserting a new element, the heap property is violated. Which of the following is the most likely cause?

medium

A. Heapify down was called instead of heapify up after insertion

B. Element was inserted at the root instead of the end

C. Heapify up was called twice

D. Heapify down was not called after extraction

Solution

1. Step 1: Understand insertion in Max Heap

   Insertion adds element at the end and restores heap by heapifying up.

2. Step 2: Identify error from heapify direction

   Calling heapify down after insertion won't fix the heap property properly, causing violation.

3. Final Answer:

   Heapify down was called instead of heapify up after insertion -> Option A

4. Quick Check:

   Insert needs heapify up, not down [OK]

Hint: Insertion needs heapify up, not down [OK]

Common Mistakes:

• Inserting at root directly
• Confusing heapify directions
• Ignoring heapify after insertion

5. You need to design a system that always returns the median of a stream of numbers efficiently. Which combination of heaps is best to use and why?

hard

A. One Max Heap for lower half and one Min Heap for upper half

B. Two Max Heaps to store all numbers

C. One Min Heap for lower half and one Max Heap for upper half

D. Two Min Heaps to store all numbers

Solution

1. Step 1: Understand median calculation from stream

   Median splits data into lower half and upper half; median is middle value(s).

2. Step 2: Use Max Heap for lower half and Min Heap for upper half

   Max Heap keeps largest of lower half, Min Heap keeps smallest of upper half, enabling quick median calculation.

3. Final Answer:

   One Max Heap for lower half and one Min Heap for upper half -> Option A

4. Quick Check:

   Median = Max Heap (low) + Min Heap (high) [OK]

Hint: Median needs Max Heap low + Min Heap high [OK]

Common Mistakes:

• Using two heaps of same type
• Mixing heap roles incorrectly
• Not balancing heaps sizes