Heaps and Priority Queues Questions

To support decrease-key for Dijkstra efficiently use an indexed binary heap (min-heap) that maintains a map from item -> index so you can update a key and sift up in O(log n). Alternative is lazy insertion (push duplicate entries and ignore stale pops) which simplifies implementation but increases memory and pop overhead.

Approach:

1. IndexedHeap (min-heap) with slice of nodes {id, dist} and a map[id]int -> index.
2. DecreaseKey: update dist, siftUp from index.
3. Pop: remove root, swap with last, update map, siftDown.

Example (Go):

package pq

import "sync"

type Node struct {
	ID   int
	Dist int
}

type IndexedHeap struct {
	items []Node
	pos   map[int]int
	mu    sync.Mutex // protect for concurrent access
}

func New() *IndexedHeap { return &IndexedHeap{pos: make(map[int]int)} }

func (h *IndexedHeap) Len() int { return len(h.items) }

func (h *IndexedHeap) swap(i, j int) {
	h.items[i], h.items[j] = h.items[j], h.items[i]
	h.pos[h.items[i].ID] = i
	h.pos[h.items[j].ID] = j
}

func (h *IndexedHeap) push(n Node) {
	h.items = append(h.items, n)
	h.pos[n.ID] = len(h.items)-1
	h.siftUp(len(h.items)-1)
}

func (h *IndexedHeap) Pop() (Node, bool) {
	if len(h.items)==0 { return Node{}, false }
	n := h.items[0]
	last := len(h.items)-1
	h.swap(0, last)
	h.items = h.items[:last]
	delete(h.pos, n.ID)
	if len(h.items)>0 { h.siftDown(0) }
	return n, true
}

func (h *IndexedHeap) DecreaseKey(id, newDist int) bool {
	h.mu.Lock(); defer h.mu.Unlock()
	idx, ok := h.pos[id]; if !ok { return false }
	if newDist >= h.items[idx].Dist { return false }
	h.items[idx].Dist = newDist
	h.siftUp(idx)
	return true
}

// Implement siftUp and siftDown (omitted for brevity)

Key points:

• Time: push/pop/decrease-key O(log n). Lookup O(1) via map.
• Memory: extra O(n) for index map; lazy insertion trades that for potential O(m log n) extra where m is duplicates.
• Concurrency: protect heap+map with Mutex for correctness. For high contention, consider:
  • Sharded heaps (partition by node id) to reduce lock hot spots.
  • Single goroutine owning the heap and communicate via channels (actor model) to serialize ops — simpler correctness and often faster under contention.
  • Use read-heavy patterns with RWMutex if many reads, but decrease-key and pop are writes.
• Edge cases: absent ID on decrease, duplicates, integer overflow for distances.
• Practical SRE note: for large graphs from telemetry, lazy insertion often wins when decrease operations are infrequent relative to pushes/pops, or memory is abundant. For strict performance/predictability in Dijkstra, use indexed heap.