从优先级队列中删除元素

Question

// 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（

Answer 1

你的问题不够清楚。我假设您希望< code>maxSlidingWindow的行为如下:

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

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

为了实现这一点，可以采取以下措施：

>

用数字中的前 k 个值填充优先级队列。

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

从队列中获取最大值，将其附加到结果。

对于i从k到len（Data）-1：

> < li>

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

您应该使用heap.Remove来删除元素。Go的heap.Fix提供了一种结合删除和推送步骤的方法。

取已修改优先级队列的最大值，将其附加到结果中。

此外，您的队列实现有一个缺陷:

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
}

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

从优先级队列中丢弃数字[i-k] 元素，然后推送到队列数字[i]

使用Go的< code >堆，修改一个项目(用< code >堆。修复)或移除一个(使用< code >堆。Remove时，需要该项目的索引。要得到相应的指数，至少有两种方法。

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

非常简单。通过这种方式，您可以简化优先级队列类型：

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
}

它能正确处理重复值。

下面只是一种可能的方法，可能没有那么优雅。我使用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.
}