Heaps

learnings

Programming

Heaps

Heaps are a specialized tree-based data structure that satisfy heap properties, making them particularly useful for priority queue implementations and efficient sorting algorithms.

Overview of Heaps

Types of Heaps:

Min Heap: In a min heap, the value of each node is greater than or equal to the value of its parent, with the minimum value at the root.

Max Heap: In a max heap, the value of each node is less than or equal to the value of its parent, with the maximum value at the root.

Structure: Heaps are usually implemented as binary trees, but they are typically handled in array form for efficiency and ease of access.
Properties:

Complete Binary Tree: A heap must be a complete binary tree, meaning all levels of the tree are fully filled except possibly the last level, which is filled from left to right.
Heap Order Property: Every node’s value is greater than (or equal to) the value of its children in a max heap, and less than (or equal to) in a min heap.

Common Operations and Their Big O Notation

Operation	Time Complexity	Comments
Insert	O(log n)	Insertion in a heap involves adding the new element at the end and then “heapifying up.”
Extract Min/Max	O(log n)	Removing the min/max involves removing the root and then “heapifying down.”
Find Min/Max	O(1)	The min/max value is always at the root in a min/max heap.
Heapify	O(n)	Converting an array into a heap has a linear time complexity.
Increase Key/Decrease Key	O(log n)	Updating the value of a node may require “heapifying up” or “heapifying down.”

Heapify

Heapify adjusts a subtree to maintain the heap property: for a max heap, every parent node is greater than or equal to its children; for a min heap, every parent node is less than or equal to its children. The operation is applied in a bottom-up manner, starting from the last non-leaf node all the way up to the root node.

Given an array representation of a heap:

The parent of any element at index i is at index (i-1)/2.
Its left child is located at index 2*i + 1.
Its right child is at 2*i + 2.

Here’s how a heapify function can be implemented in Go for a max heap. This function ensures that the subtree rooted at index i is a max heap:

func heapify(arr []int, n, i int) {
    largest := i // Initialize largest as root
    l := 2*i + 1
    r := 2*i + 2

    // If left child is larger than root
    if l < n && arr[l] > arr[largest] {
        largest = l
    }

    // If right child is larger than largest so far
    if r < n && arr[r] > arr[largest] {
        largest = r
    }

    // If largest is not root
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i] // Swap

        // Recursively heapify the affected subtree
        heapify(arr, n, largest)
    }
}

Code Representation

max_heap.go

package main

import (
    "fmt"
    "math"
)

type MaxHeap struct {
    array []int
}

// Insert adds an element to the heap
func (h *MaxHeap) Insert(key int) {
    h.array = append(h.array, key)
    h.heapifyUp(len(h.array) - 1)
}

// Extract returns and removes the largest element from the heap
func (h *MaxHeap) Extract() int {
    if len(h.array) == 0 {
        fmt.Println("Heap is empty")
        return math.MinInt64
    }
    extracted := h.array[0]
    // Move the last element to the root
    h.array[0] = h.array[len(h.array)-1]
    h.array = h.array[:len(h.array)-1]
    h.heapifyDown(0)
    return extracted
}

// Find searches for an element in the heap and returns its index or -1 if not found
func (h *MaxHeap) Find(key int) int {
    for i, val := range h.array {
        if val == key {
            return i
        }
    }
    return -1 // Not found
}

// heapifyUp adjusts the heap after insertion
func (h *MaxHeap) heapifyUp(index int) {
    for h.array[parent(index)] < h.array[index] {
        h.swap(parent(index), index)
        index = parent(index)
    }
}

// heapifyDown adjusts the heap after extraction
func (h *MaxHeap) heapifyDown(index int) {
    lastIndex := len(h.array) - 1
    l, r := left(index), right(index)
    childToCompare := 0

    for l <= lastIndex {
        if l == lastIndex { // When left child is the only child
            childToCompare = l
        } else if h.array[l] > h.array[r] { // When left child is larger
            childToCompare = l
        } else { // When right child is larger
            childToCompare = r
        }

        // Swap if the current node is smaller than the larger child
        if h.array[index] < h.array[childToCompare] {
            h.swap(index, childToCompare)
            index = childToCompare
            l, r = left(index), right(index)
        } else {
            return
        }
    }
}

// IncreaseKey increases the value of an element and adjusts the heap
func (h *MaxHeap) IncreaseKey(index, newValue int) {
    if index < 0 || index >= len(h.array) {
        fmt.Println("Index out of bounds")
        return
    }
    h.array[index] = newValue
    h.heapifyUp(index)
}

// Helper functions
func parent(i int) int { return (i - 1) / 2 }
func left(i int) int   { return 2*i + 1 }
func right(i int) int  { return 2*i + 2 }
func (h *MaxHeap) swap(i1, i2 int) {
    h.array[i1], h.array[i2] = h.array[i2], h.array[i1]
}

func main() {
    heap := &MaxHeap{}
    fmt.Println("Inserting elements into heap:")
    heap.Insert(3)
    heap.Insert(4)
    heap.Insert(9)
    heap.Insert(5)
    heap.Insert(2

Trees Graphs