Heap Extract Min or Max Bubble Down in DSA Go - Build from Scratch

Heap Extract Min or Max Bubble Down

📖 Scenario: You are managing a priority queue using a heap data structure. You want to remove the top element (minimum for min-heap or maximum for max-heap) and then restore the heap property by moving the new root element down the tree.

🎯 Goal: Build a Go program that extracts the root element from a heap and restores the heap property by bubbling down the new root element.

📋 What You'll Learn

Create a slice called heap with exact values representing a heap

Create a variable called heapSize to track the current size of the heap

Write a function bubbleDown that restores the heap property by moving the root element down

Extract the root element by replacing it with the last element and reducing heapSize

Print the heap slice after extraction and bubbling down

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling tasks, and algorithms like Dijkstra's shortest path.

💼 Career

Understanding heap extraction and bubble down is essential for roles involving algorithm optimization and system design.

1

Create the initial heap slice

Create a slice called heap with these exact integer values: 10, 15, 20, 17, 25. Also create an integer variable called heapSize and set it to 5.

DSA Go

# Create the heap slice and heapSize variable
# Your code here

Hint

Use heap := []int{10, 15, 20, 17, 25} and heapSize := 5.

2

Write the bubbleDown function

Write a function called bubbleDown that takes a slice of integers called heap and an integer heapSize. It should restore the min-heap property by moving the element at index 0 down the heap until it is smaller than its children or it reaches a leaf. Use variables index, leftChild, rightChild, and smallest inside the function.

DSA Go

package main

import "fmt"

func main() {
    heap := []int{10, 15, 20, 17, 25}
    heapSize := 5
}

// Write bubbleDown function below
// Your code here

Hint

Use a loop to compare the current element with its children and swap if needed.

3

Extract the root and call bubbleDown

Inside main, replace the root element heap[0] with the last element heap[heapSize-1], then decrease heapSize by 1. Then call bubbleDown(heap, heapSize) to restore the heap property.

DSA Go

package main

import "fmt"

func main() {
    heap := []int{10, 15, 20, 17, 25}
    heapSize := 5

    // Extract root and call bubbleDown
    // Your code here
}

func bubbleDown(heap []int, heapSize int) {
    index := 0
    for {
        leftChild := 2*index + 1
        rightChild := 2*index + 2
        smallest := index

        if leftChild < heapSize && heap[leftChild] < heap[smallest] {
            smallest = leftChild
        }
        if rightChild < heapSize && heap[rightChild] < heap[smallest] {
            smallest = rightChild
        }

        if smallest == index {
            break
        }

        heap[index], heap[smallest] = heap[smallest], heap[index]
        index = smallest
    }
}

Hint

Replace root with last element, reduce heapSize, then call bubbleDown.

4

Print the heap after extraction

Add a fmt.Println(heap[:heapSize]) statement at the end of main to print the heap slice after extraction and bubbling down.

DSA Go

package main

import "fmt"

func main() {
    heap := []int{10, 15, 20, 17, 25}
    heapSize := 5

    heap[0] = heap[heapSize-1]
    heapSize--
    bubbleDown(heap, heapSize)

    // Print the heap slice after extraction
    // Your code here
}

func bubbleDown(heap []int, heapSize int) {
    index := 0
    for {
        leftChild := 2*index + 1
        rightChild := 2*index + 2
        smallest := index

        if leftChild < heapSize && heap[leftChild] < heap[smallest] {
            smallest = leftChild
        }
        if rightChild < heapSize && heap[rightChild] < heap[smallest] {
            smallest = rightChild
        }

        if smallest == index {
            break
        }

        heap[index], heap[smallest] = heap[smallest], heap[index]
        index = smallest
    }
}

Hint

Use fmt.Println(heap[:heapSize]) to print the current heap slice.