Why Heap Exists and What Sorted Array Cannot Do Efficiently in DSA Go - See It Work

Why Heap Exists and What Sorted Array Cannot Do Efficiently

📖 Scenario: Imagine you are managing a list of tasks with different priorities. You want to always pick the highest priority task quickly. You tried using a sorted list, but it takes too long to add new tasks while keeping the list sorted.

🎯 Goal: Build a simple program to show how adding tasks to a sorted array is slow, and how a heap can help by allowing faster insertion and quick access to the highest priority task.

📋 What You'll Learn

Create a sorted array of tasks with priorities

Add a new task to the sorted array and keep it sorted

Create a max heap of tasks

Add a new task to the heap

Show the difference in efficiency by printing the task lists

💡 Why This Matters

🌍 Real World

Task scheduling systems, priority queues in operating systems, and event management often need fast access to highest priority items.

💼 Career

Understanding heaps helps in roles involving system design, backend development, and algorithm optimization.

1

Create a sorted array of tasks with priorities

Create a variable called sortedTasks which is a slice of integers with these exact values in ascending order: 10, 20, 30, 40, 50

DSA Go

# Your code here

Hint

Use a slice literal to create sortedTasks with the given numbers in order.

2

Add a new task to the sorted array and keep it sorted

Add a new task with priority 35 to the sortedTasks slice and keep the slice sorted in ascending order. Use a variable called newTask for the new priority and insert it in the correct position.

DSA Go

package main

import "fmt"

func main() {
    sortedTasks := []int{10, 20, 30, 40, 50}
    // Your code here
}

Hint

Find the correct index where newTask fits, then use append to insert it.

3

Create a max heap of tasks and add a new task

Create a max heap using a slice called heapTasks with these exact values: 50, 40, 30, 20, 10. Then add a new task with priority 35 to the heap by appending it and reordering the heap using a function called heapifyUp.

DSA Go

package main

import "fmt"

func main() {
    sortedTasks := []int{10, 20, 30, 40, 50}
    newTask := 35
    index := 0
    for i, val := range sortedTasks {
        if val > newTask {
            index = i
            break
        }
        index = i + 1
    }
    sortedTasks = append(sortedTasks[:index], append([]int{newTask}, sortedTasks[index:]...)...)

    // Your code here
}

Hint

Use a helper function heapifyUp to reorder the heap after adding the new task.

4

Print the sorted array and heap after adding the new task

Print the sortedTasks slice and the heapTasks slice using fmt.Println to show their states after adding the new task.

DSA Go

package main

import "fmt"

func heapifyUp(heap []int, index int) {
    for index > 0 {
        parent := (index - 1) / 2
        if heap[parent] >= heap[index] {
            break
        }
        heap[parent], heap[index] = heap[index], heap[parent]
        index = parent
    }
}

func main() {
    sortedTasks := []int{10, 20, 30, 40, 50}
    newTask := 35
    index := 0
    for i, val := range sortedTasks {
        if val > newTask {
            index = i
            break
        }
        index = i + 1
    }
    sortedTasks = append(sortedTasks[:index], append([]int{newTask}, sortedTasks[index:]...)...)

    heapTasks := []int{50, 40, 30, 20, 10}
    heapTasks = append(heapTasks, newTask)
    heapifyUp(heapTasks, len(heapTasks)-1)

    // Your code here
}

Hint

Use fmt.Println to print both slices with labels.