Remove element from the Priority queue

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 

     }

}

I am trying to print the maximum value in a sliding window. Putting the elements of window size, here k = 3 into the priority queue(Maxheap) and then peek the value. "heap.Init(&pq)" will assign the index in pq based on the priority. Look for maxSlidingWindow function, the last for loop prints the max element for each window of size k. If you compare the indices in the pq and the nums array the indices will be different. And hence deleting the desired element from the priority queue seems almost impossible.

Answer 1

Your question is not clear enough. I assume that you want your maxSlidingWindow to behave like this:

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

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

To achieve this, one might do the following:

1. Fill a priority queue with the first k values from nums.

   Your code is putting all values from nums into the queue, which does not seem like a moving window approach. And I do doubt if I misunderstand your question.

2. Take the max value from the queue, append it to the result.

3. For i from k to len(Data) - 1:

   1. Discard the nums[i-k] element from the priority queue, and push into the queue nums[i].

      You should use use heap.Remove to remove an element. Go's heap.Fix provides a way to combine the removing and pushing steps.

   2. Take the max value of the modified priority queue, append it to the result.

Also, your implementation of the queue has a bug:

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
}

Removing elements from priority queues

According to the title of the question, it seems you cannot get this part working:

Discard the nums[i-k] element from the priority queue, and push into the queue nums[i]

Using Go's heap, to modify an item (with heap.Fix) or remove one (with heap.Remove, an index to that item is required. To get the corresponding index, there are at least two ways.

Note that we need to distinguish from the indices of elements in nums and the indices of elements in the queue. I am to refer to the former one as i in the following code and the latter, j. We know the i of the element we want to remove, but since heap changes the queue, we need to find j.

Loop through the queue and find the element

Simple enough. In this way, you may just simplify the PriorityQueue type:

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
}

It handles duplicate values correctly.

Keep a external i -> j mapping

Below is just a possible way doing it and may not be that elegant. I use a CircularArray to keep our mapping:

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.
}