資料結構
網路
關係資料庫管理系統(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 次瀏覽
