資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Go語言實現雙端優先佇列程式
雙端優先佇列（簡稱DEPQ）是一種擴充套件了標準優先佇列功能的資料結構。在本文中，我們將使用兩種方法在Go語言中實現雙端優先佇列：第一種方法使用兩個獨立的堆分別表示最大優先順序和最小優先順序；第二種方法則透過在單個堆中新增額外資訊來高效地進行查詢。在程式碼示例中，我們將執行插入、檢索、刪除和更新等操作。
解釋
雙端優先佇列是一種允許插入和刪除操作，並能高效訪問集合中最大和最小元素的資料結構。
Max Heap: Min Heap: 9 3 / \ / \ 7 5 4 6 / / 3 5
在大頂堆中，根節點包含最大值[9]，每個父節點的值都大於子節點的值，從上到下值遞減。
在小頂堆中，根節點包含最小值[3]，每個父節點的值都小於子節點的值，從上到下值遞增。
演算法
初始化兩個堆，maxHeap和minHeap。
將元素與maxHeap和minHeap的根節點進行比較，以確定其優先順序。將元素插入到相應的堆中。如果堆的大小差超過1，則平衡堆。
從包含該元素的堆中刪除該元素。如果堆的大小差超過1，則平衡堆。
返回maxHeap的根節點。
返回minHeap的根節點。
語法
type DEPQ struct {
maxHeap, minHeap []int
}
DEPQ結構體包含maxHeap和minHeap切片，允許高效地檢索最高和最低優先順序元素。
type DEPQ struct {
heap []int
values map[int]int
}
該語法使用單個增強堆來實現DEPQ。DEPQ結構體包含兩個切片：heap用於儲存優先佇列中的元素，values用於跟蹤元素的位置。AugmentedHeap結構體包含heap切片，允許高效地查詢最高和最低優先順序元素。
示例1
在這個例子中，我們使用兩個獨立的堆在Go語言中實現雙端優先佇列，一個用於最大優先順序（maxHeap），另一個用於最小優先順序（minHeap）。Insert函式將元素插入到兩個堆中，而Delete函式則從兩個堆中刪除元素。GetMax和GetMin函式分別從DEPQ中檢索最大和最小元素。
package main
import (
"container/heap"
"fmt"
)
type MaxHeap []int
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
type MinHeap []int
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
type DEPQ struct {
maxHeap *MaxHeap
minHeap *MinHeap
}
func NewDEPQ() *DEPQ {
maxHeap := &MaxHeap{}
minHeap := &MinHeap{}
heap.Init(maxHeap)
heap.Init(minHeap)
return &DEPQ{maxHeap, minHeap}
}
func (dq *DEPQ) Insert(val int) {
heap.Push(dq.maxHeap, val)
heap.Push(dq.minHeap, val)
}
func (dq *DEPQ) Delete(val int) {
for i := 0; i < len(*dq.maxHeap); i++ {
if (*dq.maxHeap)[i] == val {
heap.Remove(dq.maxHeap, i)
break
}
}
for i := 0; i < len(*dq.minHeap); i++ {
if (*dq.minHeap)[i] == val {
heap.Remove(dq.minHeap, i)
break
}
}
}
func (dq *DEPQ) GetMax() int {
if len(*dq.maxHeap) > 0 {
return (*dq.maxHeap)[0]
}
return -1
}
func (dq *DEPQ) GetMin() int {
if len(*dq.minHeap) > 0 {
return (*dq.minHeap)[0]
}
return -1
}
func main() {
dq := NewDEPQ()
dq.Insert(5)
dq.Insert(3)
dq.Insert(7)
dq.Insert(4)
dq.Insert(6)
fmt.Println("Maximum element:", dq.GetMax())
fmt.Println("Minimum element:", dq.GetMin())
dq.Delete(4)
fmt.Println("Maximum element after deletion:", dq.GetMax())
fmt.Println("Minimum element after deletion:", dq.GetMin())
}
輸出
Maximum element: 7 Minimum element: 3 Maximum element after deletion: 7 Minimum element after deletion: 3
示例2
在這個例子中，我們使用單個堆來表示Go語言中的雙端優先佇列。每個元素在堆中儲存兩次，一次作為最大元素，一次作為最小元素，使用DEPQNode結構體。DEPQ結構體包含堆和一個唯一識別符號，以確保每個節點都有一個獨特的識別符號。Insert函式透過建立兩個DEPQNode例項（一個用於最大值，一個用於最小值）並將它們新增到堆中來向DEPQ新增元素。GetMaximum和GetMinimum函式分別從DEPQ中檢索最大和最小元素。Remove函式透過查詢和刪除堆中元素的兩個例項來從DEPQ中刪除指定元素。
package main
import (
"container/heap"
"fmt"
)
type DEPQNode struct {
value int
isMax, isMin bool
uniqueID int
}
type DEPQHeap []DEPQNode
func NewDEPQHeap() *DEPQHeap {
return &DEPQHeap{}
}
func (h DEPQHeap) Len() int { return len(h) }
func (h DEPQHeap) Less(i, j int) bool { return h[i].value < h[j].value }
func (h DEPQHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *DEPQHeap) Push(x interface{}) {
node := x.(DEPQNode)
*h = append(*h, node)
}
func (h *DEPQHeap) Pop() interface{} {
old := *h
n := len(old)
node := old[n-1]
*h = old[0 : n-1]
return node
}
type DoubleEndedPriorityQueue struct {
heap *DEPQHeap
}
func NewDoubleEndedPriorityQueue() *DoubleEndedPriorityQueue {
return &DoubleEndedPriorityQueue{
heap: NewDEPQHeap(),
}
}
func (dePQ *DoubleEndedPriorityQueue) Insert(value int) {
node := DEPQNode{value: value, isMax: true, isMin: true, uniqueID: len(*dePQ.heap)}
heap.Push(dePQ.heap, node)
}
func (dePQ *DoubleEndedPriorityQueue) GetMinimum() int {
if dePQ.heap.Len() == 0 {
return -1
}
return (*dePQ.heap)[0].value
}
func (dePQ *DoubleEndedPriorityQueue) GetMaximum() int {
if dePQ.heap.Len() == 0 {
return -1
}
return (*dePQ.heap)[dePQ.heap.Len()-1].value
}
func main() {
dePQ := NewDoubleEndedPriorityQueue()
dePQ.Insert(10)
dePQ.Insert(5)
dePQ.Insert(20)
fmt.Println("Minimum Element:", dePQ.GetMinimum())
fmt.Println("Maximum Element:", dePQ.GetMaximum())
}
輸出
Minimum Element: 5 Maximum Element: 20
現實生活中的應用
醫院病人管理
在醫院中，病人分診涉及根據病人的病情優先安排病人。DEPQ可以儲存病情最嚴重的病人（使用大頂堆）和病情較輕的病人（使用小頂堆）。這使得醫生能夠快速處理危重病人，同時有效地管理不太緊急的病例。
社交媒體資訊流
社交媒體平臺通常根據使用者參與度顯示帖子。DEPQ可以優先顯示點贊或評論最多的帖子（使用大頂堆）以及不太受歡迎的帖子（使用小頂堆）。這允許使用者在資訊流中看到熱門內容和不太突出的帖子，從而增強他們的瀏覽體驗。
結論
DEPQ是標準優先佇列的擴充套件，允許高效地檢索最高和最低優先順序元素。在本文中，我們將探討兩種在Go語言中實現雙端優先佇列的方法。第一種方法使用兩個獨立的堆分別表示最大和最小優先順序，而第二種方法則使用單個增強堆。程式碼示例演示了DEPQ中元素的插入、刪除和檢索，展示了它們的實際應用和效率。
瀏覽量：147
