Go语言中实现可复用优先队列的策略与实践 (Pre-Generics)

package main

import (
    "container/heap"
    "fmt"
)

// Item represents an item in the priority queue.
type Item struct {
    Value    string // The value of the item
    Priority int    // The priority of the item (lower value means higher priority)
    Index    int    // The index of the item in the heap, used by update operations
}

// PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

// Len is the number of elements in the collection.
func (pq PriorityQueue) Len() int { return len(pq) }

// Less reports whether the element with index i should sort before the element with index j.
// For a min-heap, we want lower priority values to be "less".
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Priority < pq[j].Priority
}

// Swap swaps the elements at indices i and j.
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].Index = i
    pq[j].Index = j
}

// Push adds an item to the heap.
func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item) // Type assertion
    item.Index = n
    *pq = append(*pq, item)
}

// Pop removes and returns the minimum element (highest priority) from the heap.
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil // Avoid memory leak
    item.Index = -1 // For safety, indicate item is no longer in the heap
    *pq = old[0 : n-1]
    return item
}

package main

import (
    "container/heap"
    "fmt"
)

// Item represents an item in the priority queue.
type Item struct {
    Value    string // The value of the item
    Priority int    // The priority of the item (lower value means higher priority)
    Index    int    // The index of the item in the heap, used by update operations
}

// PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

// Len is the number of elements in the collection.
func (pq PriorityQueue) Len() int { return len(pq) }

// Less reports whether the element with index i should sort before the element with index j.
// For a min-heap, we want lower priority values to be "less".
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Priority < pq[j].Priority
}

// Swap swaps the elements at indices i and j.
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].Index = i
    pq[j].Index = j
}

// Push adds an item to the heap.
func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item) // Type assertion
    item.Index = n
    *pq = append(*pq, item)
}

// Pop removes and returns the minimum element (highest priority) from the heap.
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil // Avoid memory leak
    item.Index = -1 // For safety, indicate item is no longer in the heap
    *pq = old[0 : n-1]
    return item
}

// Example usage
func main() {
    items := map[string]int{
        "task1": 3,
        "task2": 1,
        "task3": 4,
        "task4": 2,
    }

    pq := make(PriorityQueue, len(items))
    i := 0
    for value, priority := range items {
        pq[i] = &Item{
            Value:    value,
            Priority: priority,
            Index:    i,
        }
        i++
    }

    heap.Init(&pq) // Initialize the heap

    // Add a new item
    item := &Item{Value: "task5", Priority: 0}
    heap.Push(&pq, item)

    fmt.Printf("Priority Queue (min-heap) elements in order of priority:\n")
    for pq.Len() > 0 {
        item := heap.Pop(&pq).(*Item)
        fmt.Printf("  %s (Priority: %d)\n", item.Value, item.Priority)
    }
}

Priority Queue (min-heap) elements in order of priority:
  task5 (Priority: 0)
  task2 (Priority: 1)
  task4 (Priority: 2)
  task1 (Priority: 3)
  task3 (Priority: 4)