Heap Concept Structure and Properties in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this min-heap insertion sequence?

Consider a min-heap initially empty. Insert the elements in this order: 10, 4, 15, 1. What is the heap array after all insertions?

DSA Go

package main

import (
	"fmt"
)

func main() {
	heap := []int{}

	insert := func(h []int, val int) []int {
		h = append(h, val)
		idx := len(h) - 1
		for idx > 0 {
			parent := (idx - 1) / 2
			if h[parent] <= h[idx] {
				break
			}
			h[parent], h[idx] = h[idx], h[parent]
			idx = parent
		}
		return h
	}

	heap = insert(heap, 10)
	heap = insert(heap, 4)
	heap = insert(heap, 15)
	heap = insert(heap, 1)

	fmt.Println(heap)
}

A [10 4 15 1]

B [1 4 15 10]

C [4 1 15 10]

D [1 10 15 4]

💡 Hint

Remember min-heap property: parent is always smaller or equal to children.

After inserting 10, heap is [10]. Insert 4, it swaps with 10 to become [4,10]. Insert 15, placed at end [4,10,15]. Insert 1, it bubbles up to root: [1,4,15,10].

🧠 Conceptual

intermediate

Which property must a max-heap always satisfy?

Choose the correct property that defines a max-heap structure.

A All leaf nodes have the same value.

B Every parent node is less than or equal to its children.

C Every parent node is greater than or equal to its children.

D The heap is always a complete binary tree but no ordering property.

💡 Hint

Think about the largest element position in a max-heap.

A max-heap requires each parent to be greater or equal to its children, ensuring the largest element is at the root.

🔧 Debug

advanced

What error occurs when this heapify function is called with an invalid index?

Given this Go heapify function snippet, what error will occur if called with an index outside the heap array bounds?

DSA Go

func heapify(arr []int, n int, i int) {
	largest := i
	left := 2*i + 1
	right := 2*i + 2

	if left < n && arr[left] > arr[largest] {
		largest = left
	}
	if right < n && arr[right] > arr[largest] {
		largest = right
	}
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}

A runtime error: index out of range

B compilation error: undefined function heapify

C no error, function handles invalid index gracefully

D runtime error: stack overflow

💡 Hint

Check what happens if i >= n when accessing arr[i].

If i is outside the array bounds, accessing arr[i] causes a runtime panic: index out of range.

🚀 Application

advanced

How many elements are in the heap after these operations?

Start with an empty max-heap. Insert 5, 3, 8, 1, then remove the root once. How many elements remain in the heap?

A 2

B 4

C 5

D 3

💡 Hint

Each insertion adds one element; removal deletes one element.

Inserted 4 elements, then removed 1, so 4 - 1 = 3 elements remain.

❓ Predict Output

expert

What is the heap array after heap sort on [4, 10, 3, 5, 1]?

Given the array [4, 10, 3, 5, 1], after performing heap sort (using max-heap), what is the final sorted array?

DSA Go

package main

import "fmt"

func heapify(arr []int, n int, i int) {
	largest := i
	left := 2*i + 1
	right := 2*i + 2

	if left < n && arr[left] > arr[largest] {
		largest = left
	}
	if right < n && arr[right] > arr[largest] {
		largest = right
	}
	if largest != i {
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest)
	}
}

func heapSort(arr []int) {
	n := len(arr)
	for i := n/2 - 1; i >= 0; i-- {
		heapify(arr, n, i)
	}
	for i := n - 1; i > 0; i-- {
		arr[0], arr[i] = arr[i], arr[0]
		heapify(arr, i, 0)
	}
}

func main() {
	arr := []int{4, 10, 3, 5, 1}
	heapSort(arr)
	fmt.Println(arr)
}

A [1 3 4 5 10]

B [10 5 4 3 1]

C [1 4 3 5 10]

D [3 1 4 5 10]

💡 Hint

Heap sort outputs a sorted array in ascending order.

Heap sort builds a max-heap and repeatedly extracts the max to sort ascending: final sorted array is [1 3 4 5 10].