Golang 将一个元素插入优先队列

在使用Go语言时，可能会出现需要根据紧急程度号码对元素进行排序、管理紧急事件（如作业调度）等情况。在本文中，我们将编写一个Go语言程序，将一个元素插入到优先队列中。

优先队列是一种队列类型，其中每个存储的元素都有一个优先级。元素通过入队操作添加到优先队列中，并通过出队操作从队列中移除。

语法

func make ([] type, size, capacity)

在Go语言中， make 函数用于创建数组/映射，它接受要创建的变量类型、大小和容量作为参数

func append(slice, element_1, element_2…, element_N) []T

append函数用于向数组切片中添加值。它接受多个参数。第一个参数是我们希望添加值的数组，后面是要添加的值。该函数返回包含所有值的最终数组切片。

func len(v Type) int

len()函数用于获取任何参数的长度。它接受一个参数作为数据类型变量，我们希望找到其长度，并返回长度的整数值。

步骤

• 步骤1 − 该程序导入所需的包fmt和main。创建一个名为Item的结构体，其中包含两个字段：类型为string的value和类型为int的priority。

• 步骤2 − 定义一个名为PriorityQueue的类型，它是一个Item切片，用于实现优先级队列。然后，使用给定的value和priority创建一个新的Item。

• 步骤3 − 调用upHeapify方法，将新插入的项移动到堆中，并迭代给定的索引，直到堆的根部。

• 步骤4 − 在main函数中，使用make函数创建一个空的优先级队列。遍历优先级队列，并从队列中删除项并打印它们的值。

• 步骤5 − 将元素插入到优先级队列中，然后调用upHeapify函数。

• 步骤6 − 遍历优先级队列，打印其值。

• 步骤7 − 实现downHeapify函数，以恢复堆的属性。

示例1

在这个示例中，我们将编写一个Go语言程序，使用container/heap包的insert方法将一个元素插入到队列中。

package main

import (
   "container/heap"
   "fmt"
)

type Item struct {
   value    string 
   priority int    
   index    int    
}

type PriorityQueue []*Item

func (piq PriorityQueue) Len() int {
   return len(piq)
}
func (piq PriorityQueue) Less(i, j int) bool {
   return piq[i].priority < piq[j].priority
}
func (piq PriorityQueue) Swap(i, j int) {
   piq[i], piq[j] = piq[j], piq[i]
   piq[i].index = i
   piq[j].index = j
}
func (piq *PriorityQueue) Push(x interface{}) {
   item := x.(*Item)
   item.index = len(*piq)
   *piq = append(*piq, item)
}
func (piq *PriorityQueue) Pop() interface{} {
   old := *piq
   n := len(old)
   item := old[n-1]
   item.index = -1
   *piq = old[0 : n-1]
   return item
}
func (piq *PriorityQueue) Insert(value string, priority int) {
   item := &Item{
      value:    value,
      priority: priority,
   }
   heap.Push(piq, item)
}
func main() {
   piq := make(PriorityQueue, 0)

   piq.Insert("Chocolates", 30)
   piq.Insert("Fruits", 20)
   piq.Insert("Dry Fruits", 10)

   for piq.Len() > 0 {
      item := heap.Pop(&piq).(*Item)
      fmt.Printf("Value: %s, Priority: %d\n", item.value, item.priority)
   }
}

输出

Value: Dry Fruits, Priority: 10
Value: Fruits, Priority: 20
Value: Chocolates, Priority: 30

示例2

在这个示例中，我们将编写一个Go语言程序，使用二叉堆将一个元素插入到一个优先级队列中。

package main

import "fmt"

type Item struct {
    value    string
    priority int
}

type PriorityQueue []Item

func (piq *PriorityQueue) Insert(value string, priority int) {
    item := Item{
        value:    value,
        priority: priority,
    }
    *piq = append(*piq, item)
    piq.upHeapify(len(*piq) - 1)
}

func (piq *PriorityQueue) upHeapify(index int) {
    for index > 0 {
        parentIndex := (index - 1) / 2
        if (*piq)[index].priority >= (*piq)[parentIndex].priority {
            break
        }
        (*piq)[index], (*piq)[parentIndex] = (*piq)[parentIndex], (*piq)[index]
        index = parentIndex
    }
} 

func main() {
    piq := make(PriorityQueue, 0)

    piq.Insert("Chocolates", 30)
    piq.Insert("Fruits", 20)
    piq.Insert("Vegetables", 10)

    for len(piq) > 0 {
        item := piq.Pop()
        fmt.Printf("Value: %s, Priority: %d\n", item.value, item.priority)
    }
}

func (piq *PriorityQueue) Pop() Item {
    n := len(*piq)
    item := (*piq)[0]
    (*piq)[0] = (*piq)[n-1]
    *piq = (*piq)[:n-1]
    piq.downHeapify(0)
    return item
}

func (piq *PriorityQueue) downHeapify(index int) {
    n := len(*piq)
    for {
        leftChildIndex := 2*index + 1
        rightChildIndex := 2*index + 2
        smallestIndex := index

        if leftChildIndex < n && (*piq)[leftChildIndex].priority < (*piq)[smallestIndex].priority {
            smallestIndex = leftChildIndex
        }
        if rightChildIndex < n && (*piq)[rightChildIndex].priority < (*piq)[smallestIndex].priority {
            smallestIndex = rightChildIndex
        }

        if smallestIndex == index {
            break
        }

        (*piq)[index], (*piq)[smallestIndex] = (*piq)[smallestIndex], (*piq)[index]
        index = smallestIndex
    }
}

输出

Value: Vegetables, Priority: 10
Value: Fruits, Priority: 20
Value: Chocolates, Priority: 30

结论

在本文中，我们使用两个示例编译并执行了在优先队列中插入元素的程序。第一个示例中，我们使用了一个容器/堆包，第二个示例中我们使用了二叉堆来创建一个优先队列并在其中插入元素。