数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Go语言程序：向优先队列插入元素
在使用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`的结构体，其中包含两个字段：`value`（字符串类型）和`priority`（整数类型）。
步骤2 - 定义一个名为`PriorityQueue`的类型，它是一个`Item`的切片，用于实现优先队列。然后，创建一个具有给定值和优先级的新的`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
结论
在本文中，我们编译并执行了使用两个示例在优先队列中插入元素的程序。在第一个示例中，我们使用了`container/heap`包；在第二个示例中，我们使用了二叉堆来创建优先队列并在其中插入元素。
196 次浏览
