linear aging (heap) priority queue

main.go

package main

import (
	"fmt"
	"time"
)

// Item represents an item in the priority queue with aging support
type Item struct {
	Value       string        // The actual data/value
	Priority    int           // Base priority (higher = more important)
	CreatedAt   time.Time     // When the item was created
	MaxAge      time.Duration // Maximum age before priority boost kicks in
	AgingFactor float64       // How much priority increases per unit time
}

// EffectivePriority calculates the current effective priority including aging
func (item *Item) EffectivePriority() float64 {
	age := time.Since(item.CreatedAt)
	agingBoost := float64(age.Nanoseconds()) / float64(item.MaxAge.Nanoseconds()) * item.AgingFactor
	return float64(item.Priority) + agingBoost
}

// LinearAgingPriorityQueue implements a heap-based priority queue with linear aging
type LinearAgingPriorityQueue struct {
	items []*Item
}

// NewLinearAgingPriorityQueue creates a new priority queue
func NewLinearAgingPriorityQueue() *LinearAgingPriorityQueue {
	return &LinearAgingPriorityQueue{
		items: make([]*Item, 0),
	}
}

// Len returns the number of items in the queue
func (pq *LinearAgingPriorityQueue) Len() int {
	return len(pq.items)
}

// parent returns the parent index of node at index i
func (pq *LinearAgingPriorityQueue) parent(i int) int {
	return (i - 1) / 2
}

// leftChild returns the left child index of node at index i
func (pq *LinearAgingPriorityQueue) leftChild(i int) int {
	return 2*i + 1
}

// rightChild returns the right child index of node at index i
func (pq *LinearAgingPriorityQueue) rightChild(i int) int {
	return 2*i + 2
}

// swap swaps two items in the heap
func (pq *LinearAgingPriorityQueue) swap(i, j int) {
	pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
}

// heapifyUp maintains heap property by moving item up
func (pq *LinearAgingPriorityQueue) heapifyUp(index int) {
	for index > 0 {
		parentIndex := pq.parent(index)
		if pq.items[index].EffectivePriority() <= pq.items[parentIndex].EffectivePriority() {
			break
		}
		pq.swap(index, parentIndex)
		index = parentIndex
	}
}

// heapifyDown maintains heap property by moving item down
func (pq *LinearAgingPriorityQueue) heapifyDown(index int) {
	for {
		maxIndex := index
		leftIndex := pq.leftChild(index)
		rightIndex := pq.rightChild(index)

		// Find the index with maximum effective priority
		if leftIndex < len(pq.items) &&
			pq.items[leftIndex].EffectivePriority() > pq.items[maxIndex].EffectivePriority() {
			maxIndex = leftIndex
		}

		if rightIndex < len(pq.items) &&
			pq.items[rightIndex].EffectivePriority() > pq.items[maxIndex].EffectivePriority() {
			maxIndex = rightIndex
		}

		if maxIndex == index {
			break
		}

		pq.swap(index, maxIndex)
		index = maxIndex
	}
}

// Push adds a new item to the priority queue
func (pq *LinearAgingPriorityQueue) Push(value string, priority int, maxAge time.Duration, agingFactor float64) {
	item := &Item{
		Value:       value,
		Priority:    priority,
		CreatedAt:   time.Now(),
		MaxAge:      maxAge,
		AgingFactor: agingFactor,
	}

	pq.items = append(pq.items, item)
	pq.heapifyUp(len(pq.items) - 1)
}

// Pop removes and returns the item with highest effective priority
func (pq *LinearAgingPriorityQueue) Pop() *Item {
	if len(pq.items) == 0 {
		return nil
	}

	// Store the root (highest priority item)
	root := pq.items[0]

	// Move last item to root and remove last item
	lastIndex := len(pq.items) - 1
	pq.items[0] = pq.items[lastIndex]
	pq.items = pq.items[:lastIndex]

	// Restore heap property if items remain
	if len(pq.items) > 0 {
		pq.heapifyDown(0)
	}

	return root
}

// Peek returns the item with highest effective priority without removing it
func (pq *LinearAgingPriorityQueue) Peek() *Item {
	if len(pq.items) == 0 {
		return nil
	}
	return pq.items[0]
}

// IsEmpty returns true if the queue is empty
func (pq *LinearAgingPriorityQueue) IsEmpty() bool {
	return len(pq.items) == 0
}

// UpdatePriorities recalculates effective priorities and rebuilds heap
// This should be called periodically to account for aging
func (pq *LinearAgingPriorityQueue) UpdatePriorities() {
	// Rebuild the heap from bottom up to account for changed priorities
	for i := len(pq.items)/2 - 1; i >= 0; i-- {
		pq.heapifyDown(i)
	}
}

// PrintQueue displays current queue state with priorities and aging info
func (pq *LinearAgingPriorityQueue) PrintQueue() {
	fmt.Printf("\n=== Priority Queue State (Total: %d items) ===\n", len(pq.items))
	if len(pq.items) == 0 {
		fmt.Println("Queue is empty")
		return
	}

	for i, item := range pq.items {
		age := time.Since(item.CreatedAt)
		effectivePriority := item.EffectivePriority()
		agingBoost := effectivePriority - float64(item.Priority)

		fmt.Printf("Index %d: '%s' | Base Priority: %d | Age: %v | Aging Boost: %.2f | Effective Priority: %.2f\n",
			i, item.Value, item.Priority, age.Round(time.Millisecond), agingBoost, effectivePriority)
	}
	fmt.Println()
}

func main() {
	fmt.Println("Linear Aging Priority Queue Demonstration")
	fmt.Println("=========================================")

	// Create priority queue
	pq := NewLinearAgingPriorityQueue()

	// Configure aging parameters
	maxAge := 5 * time.Second // Items become "old" after 5 seconds
	agingFactor := 10.0       // Each maxAge period adds 10 to effective priority

	fmt.Printf("\nConfiguration:")
	fmt.Printf("\n- Max Age: %v", maxAge)
	fmt.Printf("\n- Aging Factor: %.1f (priority boost per max age period)", agingFactor)
	fmt.Printf("\n- Aging Formula: EffectivePriority = BasePriority + (Age/MaxAge) * AgingFactor\n")

	// Scenario 1: Demonstrate basic priority queue behavior
	fmt.Println("\n1. Adding items with different priorities:")
	pq.Push("High Priority Task", 10, maxAge, agingFactor)
	pq.Push("Medium Priority Task", 5, maxAge, agingFactor)
	pq.Push("Low Priority Task", 1, maxAge, agingFactor)
	pq.PrintQueue()

	// Scenario 2: Process some items to show normal priority order
	fmt.Println("2. Processing items in normal priority order:")
	for i := 0; i < 2 && !pq.IsEmpty(); i++ {
		item := pq.Pop()
		fmt.Printf("Processed: '%s' (Effective Priority: %.2f)\n", item.Value, item.EffectivePriority())
	}
	pq.PrintQueue()

	// Scenario 3: Add a new high priority item
	fmt.Println("3. Adding new high priority item:")
	pq.Push("URGENT NEW TASK", 15, maxAge, agingFactor)
	pq.PrintQueue()

	// Scenario 4: Wait and show aging effect
	fmt.Println("4. Waiting 6 seconds to demonstrate aging...")
	time.Sleep(6 * time.Second)

	// Update priorities to account for aging
	pq.UpdatePriorities()
	pq.PrintQueue()

	fmt.Println("5. Notice how the old low priority task now has higher effective priority!")
	fmt.Println("   This prevents starvation - older items get processed even if new high priority items arrive.")

	// Scenario 5: Add another new high priority item to show continued aging protection
	fmt.Println("\n6. Adding another new high priority item:")
	pq.Push("ANOTHER URGENT TASK", 20, maxAge, agingFactor)
	pq.UpdatePriorities()
	pq.PrintQueue()

	// Process remaining items
	fmt.Println("7. Processing all remaining items to see final order:")
	for !pq.IsEmpty() {
		item := pq.Pop()
		fmt.Printf("Processed: '%s' (Base Priority: %d, Effective Priority: %.2f, Age: %v)\n",
			item.Value, item.Priority, item.EffectivePriority(), time.Since(item.CreatedAt).Round(time.Millisecond))
	}

	fmt.Println("\n8. Demonstration of more complex aging scenario:")
	demonstrateStarvationPrevention(maxAge, agingFactor)
}

// demonstrateStarvationPrevention shows a more complex scenario where
// continuous high-priority items could starve low-priority ones without aging
func demonstrateStarvationPrevention(maxAge time.Duration, agingFactor float64) {
	fmt.Println("\nComplex Starvation Prevention Scenario:")
	fmt.Println("--------------------------------------")

	pq2 := NewLinearAgingPriorityQueue()

	// Add initial low priority items
	pq2.Push("Background Job A", 1, maxAge, agingFactor)
	pq2.Push("Background Job B", 2, maxAge, agingFactor)

	fmt.Println("Initial state with background jobs:")
	pq2.PrintQueue()

	// Simulate a scenario where high priority items keep coming
	fmt.Println("Simulating continuous arrival of high priority items...")

	for round := 1; round <= 3; round++ {
		fmt.Printf("\n--- Round %d ---\n", round)

		// Add high priority items
		pq2.Push(fmt.Sprintf("Critical Task %d", round), 20, maxAge, agingFactor)

		// Wait a bit to let aging take effect
		time.Sleep(2 * time.Second)
		pq2.UpdatePriorities()

		fmt.Printf("After adding Critical Task %d and waiting 2s:\n", round)
		pq2.PrintQueue()

		// Process one item
		if !pq2.IsEmpty() {
			item := pq2.Pop()
			fmt.Printf("Processed: '%s' (Base: %d, Effective: %.2f, Age: %v)\n",
				item.Value, item.Priority, item.EffectivePriority(),
				time.Since(item.CreatedAt).Round(time.Millisecond))
		}
	}

	fmt.Println("\nFinal queue state:")
	pq2.PrintQueue()

	fmt.Println("Conclusion: Notice how background jobs eventually get processed")
	fmt.Println("despite continuous arrival of high priority items, thanks to aging!")
}

output.txt

Linear Aging Priority Queue Demonstration
=========================================

Configuration:
- Max Age: 5s
- Aging Factor: 10.0 (priority boost per max age period)
- Aging Formula: EffectivePriority = BasePriority + (Age/MaxAge) * AgingFactor

1. Adding items with different priorities:

=== Priority Queue State (Total: 3 items) ===
Index 0: 'High Priority Task' | Base Priority: 10 | Age: 0s | Aging Boost: 0.00 | Effective Priority: 10.00
Index 1: 'Medium Priority Task' | Base Priority: 5 | Age: 0s | Aging Boost: 0.00 | Effective Priority: 5.00
Index 2: 'Low Priority Task' | Base Priority: 1 | Age: 0s | Aging Boost: 0.00 | Effective Priority: 1.00

2. Processing items in normal priority order:
Processed: 'High Priority Task' (Effective Priority: 10.00)
Processed: 'Medium Priority Task' (Effective Priority: 5.00)

=== Priority Queue State (Total: 1 items) ===
Index 0: 'Low Priority Task' | Base Priority: 1 | Age: 0s | Aging Boost: 0.00 | Effective Priority: 1.00

3. Adding new high priority item:

=== Priority Queue State (Total: 2 items) ===
Index 0: 'URGENT NEW TASK' | Base Priority: 15 | Age: 0s | Aging Boost: 0.00 | Effective Priority: 15.00
Index 1: 'Low Priority Task' | Base Priority: 1 | Age: 0s | Aging Boost: 0.00 | Effective Priority: 1.00

4. Waiting 6 seconds to demonstrate aging...

=== Priority Queue State (Total: 2 items) ===
Index 0: 'URGENT NEW TASK' | Base Priority: 15 | Age: 6.001s | Aging Boost: 12.00 | Effective Priority: 27.00
Index 1: 'Low Priority Task' | Base Priority: 1 | Age: 6.002s | Aging Boost: 12.00 | Effective Priority: 13.00

5. Notice how the old low priority task now has higher effective priority!
   This prevents starvation - older items get processed even if new high priority items arrive.

6. Adding another new high priority item:

=== Priority Queue State (Total: 3 items) ===
Index 0: 'URGENT NEW TASK' | Base Priority: 15 | Age: 6.002s | Aging Boost: 12.00 | Effective Priority: 27.00
Index 1: 'Low Priority Task' | Base Priority: 1 | Age: 6.002s | Aging Boost: 12.00 | Effective Priority: 13.00
Index 2: 'ANOTHER URGENT TASK' | Base Priority: 20 | Age: 0s | Aging Boost: 0.00 | Effective Priority: 20.00

7. Processing all remaining items to see final order:
Processed: 'URGENT NEW TASK' (Base Priority: 15, Effective Priority: 27.00, Age: 6.002s)
Processed: 'ANOTHER URGENT TASK' (Base Priority: 20, Effective Priority: 20.00, Age: 0s)
Processed: 'Low Priority Task' (Base Priority: 1, Effective Priority: 13.00, Age: 6.002s)

8. Demonstration of more complex aging scenario:

Complex Starvation Prevention Scenario:
--------------------------------------
Initial state with background jobs:

=== Priority Queue State (Total: 2 items) ===
Index 0: 'Background Job B' | Base Priority: 2 | Age: 0s | Aging Boost: 0.00 | Effective Priority: 2.00
Index 1: 'Background Job A' | Base Priority: 1 | Age: 0s | Aging Boost: 0.00 | Effective Priority: 1.00

Simulating continuous arrival of high priority items...

--- Round 1 ---
After adding Critical Task 1 and waiting 2s:

=== Priority Queue State (Total: 3 items) ===
Index 0: 'Critical Task 1' | Base Priority: 20 | Age: 2.001s | Aging Boost: 4.00 | Effective Priority: 24.00
Index 1: 'Background Job A' | Base Priority: 1 | Age: 2.002s | Aging Boost: 4.00 | Effective Priority: 5.00
Index 2: 'Background Job B' | Base Priority: 2 | Age: 2.002s | Aging Boost: 4.00 | Effective Priority: 6.00

Processed: 'Critical Task 1' (Base: 20, Effective: 24.00, Age: 2.001s)

--- Round 2 ---
After adding Critical Task 2 and waiting 2s:

=== Priority Queue State (Total: 3 items) ===
Index 0: 'Critical Task 2' | Base Priority: 20 | Age: 2.001s | Aging Boost: 4.00 | Effective Priority: 24.00
Index 1: 'Background Job A' | Base Priority: 1 | Age: 4.003s | Aging Boost: 8.01 | Effective Priority: 9.01
Index 2: 'Background Job B' | Base Priority: 2 | Age: 4.003s | Aging Boost: 8.01 | Effective Priority: 10.01

Processed: 'Critical Task 2' (Base: 20, Effective: 24.00, Age: 2.001s)

--- Round 3 ---
After adding Critical Task 3 and waiting 2s:

=== Priority Queue State (Total: 3 items) ===
Index 0: 'Critical Task 3' | Base Priority: 20 | Age: 2.001s | Aging Boost: 4.00 | Effective Priority: 24.00
Index 1: 'Background Job A' | Base Priority: 1 | Age: 6.004s | Aging Boost: 12.01 | Effective Priority: 13.01
Index 2: 'Background Job B' | Base Priority: 2 | Age: 6.004s | Aging Boost: 12.01 | Effective Priority: 14.01

Processed: 'Critical Task 3' (Base: 20, Effective: 24.00, Age: 2.001s)

Final queue state:

=== Priority Queue State (Total: 2 items) ===
Index 0: 'Background Job B' | Base Priority: 2 | Age: 6.004s | Aging Boost: 12.01 | Effective Priority: 14.01
Index 1: 'Background Job A' | Base Priority: 1 | Age: 6.004s | Aging Boost: 12.01 | Effective Priority: 13.01

Conclusion: Notice how background jobs eventually get processed
despite continuous arrival of high priority items, thanks to aging!