Heap Insert Operation Bubble Up in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a new value into the heap array.

DSA Go

func (h *Heap) Insert(val int) {
    h.data = append(h.data, val)
    h.bubbleUp([1])
}

Drag options to blanks, or click blank then click option'

Alen(h.data) - 1

B0

Clen(h.data)

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as the index which points to the root instead of the new element.

Using len(h.data) which is out of range since indexing starts at 0.

The new element is added at the end of the heap array, so its index is len(h.data) - 1.

2fill in blank

medium

Complete the code to find the parent index of a given child index in the heap.

DSA Go

func parentIndex(child int) int {
    return ([1] - 1) / 2
}

Drag options to blanks, or click blank then click option'

Achild

Bchild + 1

Cchild - 1

Dchild * 2

Attempts:

3 left

💡 Hint

Common Mistakes

Adding 1 to child index which shifts the calculation incorrectly.

Multiplying child index which is not how parent is calculated.

The parent index is calculated by (child - 1) / 2 in a zero-based heap array.

3fill in blank

hard

Fix the error in the bubbleUp function to correctly swap the child with its parent when needed.

DSA Go

func (h *Heap) bubbleUp(index int) {
    for index > 0 {
        parent := (index - 1) / 2
        if h.data[index] <= h.data[parent] {
            break
        }
        h.data[index], h.data[[1]] = h.data[[1]], h.data[index]
        index = parent
    }
}

Drag options to blanks, or click blank then click option'

Alen(h.data) - 1

B0

Cindex

Dparent

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping the element with itself (index).

Using 0 or last index which are unrelated to the current swap.

We swap the child at index with its parent at 'parent' index to maintain heap property.

4fill in blank

hard

Fill both blanks to complete the bubbleUp loop condition and update index correctly.

DSA Go

func (h *Heap) bubbleUp(index int) {
    for [1] {
        parent := (index - 1) / 2
        if h.data[index] <= h.data[parent] {
            break
        }
        h.data[index], h.data[parent] = h.data[parent], h.data[index]
        [2]
    }
}

Drag options to blanks, or click blank then click option'

Aindex > 0

Bindex < 0

Cindex = parent

Dindex = 0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop condition like index < 0 which never runs.

Not updating index or setting it to 0 prematurely.

The loop continues while index > 0, and after swapping, index is updated to parent to continue bubbling up.

5fill in blank

hard

Fill all three blanks to create a map of values to their indices for quick lookup after insertion.

DSA Go

func (h *Heap) Insert(val int) {
    h.data = append(h.data, val)
    h.bubbleUp(len(h.data) - 1)
    h.indexMap = map[int]int[1]: [2]
    h.indexMap[val] = [3]
}

Drag options to blanks, or click blank then click option'

Aval

Blen(h.data) - 1

Clen(h.data)

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using len(h.data) which is out of range for indexing.

Using 0 as index which is incorrect for the new element.

We initialize the map with the new value as key and its index (len(h.data)-1) as value, then update the map accordingly.