learnings
Programming
Data Structures
Heaps

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

  1. 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.
graph TD
    subgraph "Min Heap as Array"
        arr("Array: [2, 3, 4, 17, 19, 36, 7, 25, 100]")
    end

    subgraph "Min Heap as Tree"
        A[2] --> B[3]
        A --> C[4]
        B --> D[17]
        B --> E[19]
        C --> F[36]
        C --> G[7]
        D --> H[25]
        D --> I[100]
    end
  • 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.
graph TD
    subgraph "Max Heap as Array"
        arr("Array: [100, 19, 36, 17, 3, 25, 1, 2, 7]")
    end

    subgraph "Max Heap as Tree"
        A[100] --> B[19]
        A --> C[36]
        B --> D[17]
        B --> E[3]
        C --> F[25]
        C --> G[1]
        D --> H[2]
        D --> I[7]
    end

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

  2. 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
TreesGraphs