Golang 编写创建优先队列

优先队列是一种队列类型，其中为元素分配了优先级，具有较高优先级的元素首先被弹出，而优先级较低的元素次之。

在本文中，我们将编写Golang程序来创建优先队列。它们可以使用堆、切片、树等方式实现，并用于执行诸如将元素推入队列和从队列中移除元素等操作。

语法

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 - 创建一个Item结构体，包含三个字段：值(value)的类型为字符串(string)，优先级(priority)的类型为整数(int)，索引(index)的类型为整数(int)。

• 步骤2 - 然后，创建一个PriorityQueue类型的切片(slice)，并创建一个指针指向它。

• 步骤3 - 实现Len()方法、Less()方法、Swap()方法、Push()方法、Pop()方法。

• 步骤4 - 最后，实现更新方法(update method)，用于更新队列元素的优先级和值。

• 步骤5 - 在主函数中，创建一个空的PriorityQueue类型的优先队列piq。

• 步骤6 - 在这一步中，使用堆(heap)包的Push()函数将项目推入优先队列，并使用PriorityQueue的Update()方法更新项目的优先级。

• 步骤7 - 在这里，使用堆(heap)包从优先队列中弹出项目，直到队列为空。打印出每个弹出项目的值和优先级。

示例1

在此示例中，我们将编写一个Golang程序，使用二叉堆创建一个优先队列。项目的切片将作为指针创建。

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{}) {
   n := len(*piq)
   item := x.(*Item)
   item.index = n
   *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) Update(item *Item, value string, priority int) {
   item.value = value
   item.priority = priority
   heap.Fix(piq, item.index)
}
func main() {
   piq := make(PriorityQueue, 0)

   heap.Push(&piq, &Item{value: "Item 1", priority: 30})
   heap.Push(&piq, &Item{value: "Item 2", priority: 10})
   heap.Push(&piq, &Item{value: "Item 3", priority: 20})

   item := piq[2]
   piq.Update(item, item.value, 40)

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

输出

Value: Item 3, Priority: 40
Value: Item 1, Priority: 30
Value: Item 2, Priority: 10

示例2

在这个示例中，我们将编写一个Golang程序，使用一个Item结构体的切片来实现优先级队列。

package main

import (
   "fmt"
)
type Item struct {
   value    string 
   priority 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]
}
func (piq *PriorityQueue) Push(x interface{}) {
   item := x.(Item)
   *piq = append(*piq, item)
}
func (piq *PriorityQueue) Pop() interface{} {
   old := *piq
   n := len(old)
   item := old[n-1]
   *piq = old[0 : n-1]
   return item
}
func main() {
   piq := make(PriorityQueue, 0)


   piq.Push(Item{value: "Item 1", priority: 30})
   piq.Push(Item{value: "Item 2", priority: 10})
   piq.Push(Item{value: "Item 3", priority: 20})

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

输出

Value: Item 3, Priority: 20
Value: Item 2, Priority: 10
Value: Item 1, Priority: 3

结论

在这篇文章中，我们编写并执行了使用两个示例创建优先队列的程序。在第一个示例中，我们使用了堆来创建“priorityqueue”，在第二个示例中，我们使用了切片和自定义函数。优先队列可以用于任务调度、哈夫曼编码、迪杰斯特拉算法等等。