Introduction

In part 1 we covered Lists, in part 2 we covered Trees, and in part 3 we covered Hash Tables. Now we move to another structure that appears all the time in scheduling, pathfinding and stream processing: Heaps, and the abstract data type built on top of them: Priority Queues.

A lot of people use Priority Queues without realizing they are usually backed by a heap. If you need to repeatedly take the highest-priority or lowest-priority element efficiently, this is one of the best tools you can have.

As in previous articles, we keep the same base Container interface:

type Container interface {
  Empty() bool
  Size() int
  Clear()
  Values() []interface{}
  String() string
}

What is a Heap?

A Heap is a complete binary tree that satisfies a heap property.

There are two common types:

• Min-Heap: parent is always smaller than or equal to children.
• Max-Heap: parent is always greater than or equal to children.

The important detail: heap is not globally sorted like a balanced BST. It only guarantees order between parent and children. The root is always the minimum (min-heap) or maximum (max-heap).

Complete binary tree requirement

Heaps depend on a structural rule:

• all levels are fully filled except maybe the last one
• the last level is filled from left to right

That rule is what makes the array representation efficient.

graph TD
  N10["10"] --> N20["20"]
  N10 --> N15["15"]
  N20 --> N30["30"]
  N20 --> N40["40"]
  N15 --> N50["50"]

Array representation

Instead of storing pointers like a regular tree node structure, heaps are usually stored in a slice/array.

For index i:

• left child: 2*i + 1
• right child: 2*i + 2
• parent: (i - 1) / 2

flowchart LR
  A["Array: [10, 20, 15, 30, 40, 50]"] --> B["i=0 => value=10"]
  B --> C["left=1 => 20"]
  B --> D["right=2 => 15"]

This layout gives:

• no node allocations per insertion
• great cache locality
• compact memory usage

Core heap operations

Insert (Push)

1. Append value at the end.
2. Restore heap property with sift-up.

Sift-up compares the new node with its parent and swaps while the property is violated.

flowchart TD
  A["Append at end"] --> B["Compare with parent"]
  B --> C{"violates heap property?"}
  C -->|Yes| D["Swap with parent"]
  D --> B
  C -->|No| E["Done"]

Extract root (Pop)

1. Save root value.
2. Move last element to root.
3. Remove last position.
4. Restore heap property with sift-down.

Sift-down compares root with children and swaps with the best child until valid again.

flowchart TD
  A["Take root"] --> B["Move last element to root"]
  B --> C["sift-down from root"]
  C --> D{"child is better than parent?"}
  D -->|Yes| E["Swap and continue"]
  E --> D
  D -->|No| F["Done"]

Complexity

For a binary heap with n elements:

• Peek: O(1)
• Push: O(log n)
• Pop: O(log n)
• Build heap from array (heapify): O(n)

O(log n) comes from the tree height, and complete binary trees have height log n.

Practical Go implementation (MinHeap)

This implementation uses int for clarity and follows Container.

type MinHeap struct {
  data []int
}

func NewMinHeap(values ...int) *MinHeap {
  h := &MinHeap{data: append([]int{}, values...)}
  h.buildHeap()
  return h
}

func (h *MinHeap) Empty() bool {
  return len(h.data) == 0
}

func (h *MinHeap) Size() int {
  return len(h.data)
}

func (h *MinHeap) Clear() {
  h.data = nil
}

func (h *MinHeap) Values() []interface{} {
  values := make([]interface{}, len(h.data))
  for i, v := range h.data {
    values[i] = v
  }
  return values
}

func (h *MinHeap) String() string {
  return fmt.Sprintf("%v", h.data)
}

func (h *MinHeap) Peek() (int, bool) {
  if len(h.data) == 0 {
    return 0, false
  }
  return h.data[0], true
}

func (h *MinHeap) Push(value int) {
  h.data = append(h.data, value)
  h.siftUp(len(h.data) - 1)
}

func (h *MinHeap) Pop() (int, bool) {
  if len(h.data) == 0 {
    return 0, false
  }

  root := h.data[0]
  last := len(h.data) - 1
  h.data[0] = h.data[last]
  h.data = h.data[:last]

  if len(h.data) > 0 {
    h.siftDown(0)
  }

  return root, true
}

func (h *MinHeap) buildHeap() {
  for i := len(h.data)/2 - 1; i >= 0; i-- {
    h.siftDown(i)
  }
}

func (h *MinHeap) siftUp(i int) {
  for i > 0 {
    parent := (i - 1) / 2
    if h.data[parent] <= h.data[i] {
      break
    }
    h.data[parent], h.data[i] = h.data[i], h.data[parent]
    i = parent
  }
}

func (h *MinHeap) siftDown(i int) {
  n := len(h.data)

  for {
    left := 2*i + 1
    right := 2*i + 2
    smallest := i

    if left < n && h.data[left] < h.data[smallest] {
      smallest = left
    }
    if right < n && h.data[right] < h.data[smallest] {
      smallest = right
    }
    if smallest == i {
      break
    }

    h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
    i = smallest
  }
}

Imports used:

import "fmt"

From Heap to Priority Queue

A Priority Queue is an abstract structure where each element has a priority and extraction always returns the highest-priority (or lowest-priority) item.

Heaps are the most common implementation because they give O(log n) insertion/removal and O(1) access to the next item.

flowchart LR
  A["Priority Queue API"] --> B["Enqueue(value, priority)"]
  A --> C["Dequeue()"]
  B --> D["Heap insertion"]
  C --> E["Heap root extraction"]

Practical Go implementation (PriorityQueue)

Below we implement a min-priority queue (smaller priority number means higher priority).

type PQItem[T any] struct {
  Value    T
  Priority int
}

type PriorityQueue[T any] struct {
  heap []PQItem[T]
}

func NewPriorityQueue[T any]() *PriorityQueue[T] {
  return &PriorityQueue[T]{heap: make([]PQItem[T], 0)}
}

func (pq *PriorityQueue[T]) Empty() bool {
  return len(pq.heap) == 0
}

func (pq *PriorityQueue[T]) Size() int {
  return len(pq.heap)
}

func (pq *PriorityQueue[T]) Clear() {
  pq.heap = nil
}

func (pq *PriorityQueue[T]) Values() []interface{} {
  out := make([]interface{}, len(pq.heap))
  for i := range pq.heap {
    out[i] = pq.heap[i]
  }
  return out
}

func (pq *PriorityQueue[T]) String() string {
  return fmt.Sprintf("%v", pq.heap)
}

func (pq *PriorityQueue[T]) Enqueue(value T, priority int) {
  pq.heap = append(pq.heap, PQItem[T]{Value: value, Priority: priority})
  pq.siftUp(len(pq.heap) - 1)
}

func (pq *PriorityQueue[T]) Peek() (PQItem[T], bool) {
  if len(pq.heap) == 0 {
    return PQItem[T]{}, false
  }
  return pq.heap[0], true
}

func (pq *PriorityQueue[T]) Dequeue() (PQItem[T], bool) {
  if len(pq.heap) == 0 {
    return PQItem[T]{}, false
  }

  top := pq.heap[0]
  last := len(pq.heap) - 1
  pq.heap[0] = pq.heap[last]
  pq.heap = pq.heap[:last]

  if len(pq.heap) > 0 {
    pq.siftDown(0)
  }

  return top, true
}

func (pq *PriorityQueue[T]) siftUp(i int) {
  for i > 0 {
    parent := (i - 1) / 2
    if pq.heap[parent].Priority <= pq.heap[i].Priority {
      break
    }
    pq.heap[parent], pq.heap[i] = pq.heap[i], pq.heap[parent]
    i = parent
  }
}

func (pq *PriorityQueue[T]) siftDown(i int) {
  n := len(pq.heap)

  for {
    left := 2*i + 1
    right := 2*i + 2
    best := i

    if left < n && pq.heap[left].Priority < pq.heap[best].Priority {
      best = left
    }
    if right < n && pq.heap[right].Priority < pq.heap[best].Priority {
      best = right
    }
    if best == i {
      break
    }

    pq.heap[i], pq.heap[best] = pq.heap[best], pq.heap[i]
    i = best
  }
}

Real-world use cases

• Task scheduling: next task by deadline/priority.
• Graph algorithms: Dijkstra and A* rely on priority queues.
• Event simulation: process earliest event first.
• Rate limiting and retries: next retry by timestamp.
• Top-k streams: keep best candidates efficiently.

Heap vs Hash Table vs Balanced Tree

• Use Heap/Priority Queue when your operation is repeatedly taking the next best element.
• Use Hash Table when your operation is exact key lookup.
• Use Balanced Tree when you need sorted iteration and range operations.

Different structures optimize different questions. The right one depends on access pattern.

Conclusion

Heaps and Priority Queues are essential when order-by-priority matters more than random lookup. Their strength is predictable performance with simple operations: push, peek and pop in logarithmic time.

In this article we covered structure, properties, sift-up/sift-down mechanics, and practical Go implementations aligned with the same Container interface used through the series.

In the next part, we can move to Graphs and traversal/path algorithms, which connect naturally with priority queues.