从优先级队列中删除元素

哈喽！大家好，很高兴又见面了，我是golang学习网的一名作者，今天由我给大家带来一篇《从优先级队列中删除元素》，本文主要会讲到等等知识点，希望大家一起学习进步，也欢迎大家关注、点赞、收藏、转发! 下面就一起来看看吧！

// This example demonstrates a priority queue built using the heap interface.
package main

import (
    "container/heap"
    "fmt"
)

// An Item is something we manage in a priority queue.
type Item struct {
    value    int // The value of the item; arbitrary.
    priority int // The priority of the item in the queue.
    // The index is needed by update and is maintained by the heap.Interface methods.
    index int // The index of the item in the heap.
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    // We want Pop to give us the highest, not lowest, priority so we use greater than here.
    return pq[i].value > pq[j].value
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = j
    pq[j].index = i
}

func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value int, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index)
}

func main() {
    nums := []int{1, 3, 2, -3, 5, 3, 6, 7, 8, 9}
    k := 3
    result := maxSlidingWindow(nums, k)
    fmt.Println("result", result)
}

func maxSlidingWindow(nums []int, k int) {

    pq := make(PriorityQueue, len(nums))
    res := []int{}

    for i := 0; i < k; i++ {
        pq[i] = &Item{
            value:    nums[i],
            priority: nums[i],
            index:    i,
        }
        res = append(res, nums[i])
    }
    heap.Init(&pq)
    peek := pq[0]
    fmt.Println(peek.value) // its a maxheap and gives the largest element

    temp := heap.Pop(&pq).(*Item)
    fmt.Println("temp:", temp)

    remove := heap.Remove(&pq, 0).(*Item)
    // pq = slices.Delete(pq, 5)
    fmt.Println("remove:", remove)
    
    for i:=0;i<len(nums);i++{
    
     //remove the desired element from the priority Queue 
     // insert the next element in the Priority queue
     // peek the highest value 

     }

}

我正在尝试打印滑动窗口中的最大值。将窗口大小的元素（这里k = 3）放入优先级队列（maxheap），然后查看值。 "heap.init(&pq)"将根据优先级分配pq中的索引。查找 ma​​xslidingwindow 函数，最后一个 for 循环打印每个大小为 k 的窗口的最大元素。如果比较 pq 和 nums 数组中的索引，索引将会不同。因此从优先级队列中删除所需的元素似乎几乎是不可能的。

正确答案

你的问题不够明确。我假设您希望 maxslidingwindow 的行为如下：

maxslidingwindow([]int{1, 3, 2,-3, 5, 3, 6, 7, 8, 9}, 3)

  returns   -->     []int{3, 3, 5, 5, 6, 7, 8, 9}

要实现这一目标，可以执行以下操作：

1. 使用 nums 中的第一个 k 值填充优先级队列。

   您的代码将 nums 中的所有值放入队列中，这看起来不像移动窗口方法。我确实怀疑我是否误解了你的问题。

2. 从队列中取出最大值，将其附加到 result。

3. 对于我，从 k 到 len（数据）- 1：

   1. 从优先级队列中丢弃 nums[i-k] 元素，并将其推入队列 nums[i]。

      您应该使用 heap.remove 来删除元素。 go 的 heap.fix 提供了一种将删除和推送步骤结合起来的方法。

   2. 取修改后的优先级队列的最大值，将其附加到result。

此外，您的队列实现有一个错误：

func (pq priorityqueue) swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = j // should be: pq[i].index = i
    pq[j].index = i // should be: pq[j].index = j
}

从优先级队列中删除元素

根据问题的标题，似乎您无法使这部分工作：

使用go的heap，修改一项（使用heap.fix）或删除一项（使用heap.remove），需要该项的索引。要获取相应的索引，至少有两种方法。

请注意，我们需要区分 nums 中元素的索引和队列中元素的索引。我将在下面的代码中将前一个称为 i，而将后者称为 j。我们知道要删除的元素的 i，但是由于 heap 改变了队列，所以我们需要找到 j。

循环队列并找到元素

足够简单。这样，您就可以简化 priorityqueue 类型：

type priorityqueue []int
// i will skip the heap.interface part

func maxslidingwindow(nums []int, k int) []int {
    pq := make(priorityqueue, k)
    result := make([]int, 0, len(nums)-k+1)

    for i := 0; i < k; i++ {           // 1.
        pq[i] = nums[i]
    }

    heap.init(&pq)

    result = append(result, pq[0])     // 2.

    for i := k; i < len(nums); i++ {
        for j, value := range pq {     // 3.1.
            if value == nums[i-k] {
                pq[j] = nums[i]        // instead of removing then pushing
                heap.fix(&pq, j)       // we modify the content with heap.fix
                break
            }
        }
        result = append(result, pq[0]) // 3.2.
    }
    return result
}

它可以正确处理重复值。

保留外部 i -> j 映射

下面只是一种可能的方法，可能不太优雅。我使用 circulararray 来保留我们的映射：

type circulararray []int

func (a circulararray) wrapped(index int) int {
    return index % len(a)
}

func (a circulararray) get(index int) int {
    return a[a.wrapped(index)]
}

func (a circulararray) set(index int, value int) {
    a[a.wrapped(index)] = value
}

func (a circulararray) swap(i, j int) {
    ii, jj := a.wrapped(i), a.wrapped(j)
    a[ii], a[jj] = a[jj], a[ii]
}

type PriorityQueue struct {
    Window           []int         // The queue
    IndicesOfIndices CircularArray // `i -> j` mapping
}

// func (pq *PriorityQueue) Len() ...
func (pq *PriorityQueue) Push(x interface{}) {} // don't use
func (pq *PriorityQueue) Pop() interface{} { return nil } // don't use

func (pq *PriorityQueue) Less(a, b int) bool {
    return pq.Window[a] > pq.Window[b]
}

func (pq *PriorityQueue) Swap(a, b int) {
    pq.Window[a], pq.Window[b] = pq.Window[b], pq.Window[a]
    pq.IndicesOfIndices.Swap(a, b)
}

func maxSlidingWindow(nums []int, k int) []int {
    pq := PriorityQueue{
        Window:           make([]int, 0, k),
        IndicesOfIndices: make(CircularArray, k),
    }

    result := make([]int, 1, len(nums)-k+1)

    for i := 0; i < k; i++ {
        pq.PushWithIndex(nums[i], i)                          // 1.
    }

    heap.Init(&pq)

    result[0] = pq.Window[0]                                  // 2.

    for i := k; i < len(nums); i++ {
        result = append(result, pq.NextWithIndex(nums[i], i)) // 3.
    }

    return result
}

// Pushes into the queue and sets up the `i -> j` mapping
func (pq *PriorityQueue) PushWithIndex(value int, i int) {
    pq.IndicesOfIndices.Set(i, len(pq.Window))
    pq.Window = append(pq.Window, value)
}

// Updates the queue and returns the max element
func (pq *PriorityQueue) NextWithIndex(pushed int, i int) int {
    j := pq.IndicesOfIndices.Get(i) // 3.1.
    pq.Window[j] = pushed
    heap.Fix(pq, j)
    return pq.Window[0]             // 3.2.
}

到这里，我们也就讲完了《从优先级队列中删除元素》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！