Peeking into the top of the Priority Queue in Go?

Question

I was trying to implement a sample program using heap, and I am able to Push and Pop from the Heap. I was able to implement the Push and Pop methods and use them as follows:

import "container/heap"

type Meeting struct {
    start int
    end int
}

func NewMeeting(times []int) *Meeting {
    return &Meeting{start: times[0], end: times[1] }
}

type PQ []*Meeting

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

func (pq PQ) Less(i, j int) bool {
    return pq[i].end < pq[j].end
}

func (pq PQ) Swap(i, j int) {
    pq[i], pq[j]  = pq[j], pq[i]
}


func (pq *PQ) Push(x interface{}) {
    item := x.(*Meeting)
    *pq = append(*pq, item)
}

func (pq *PQ) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // avoid memory leak
    *pq = old[0 : n-1]
    return item
}

func minMeetingRooms(intervals [][]int) int {
    pq := make(PQ, 0)
    heap.Init(&pq)
    heap.Push(&pq, NewMeeting([]int{1, 3}))
    heap.Push(&pq, NewMeeting([]int{1, 2}))
    fmt.Println(heap.Pop(&pq).(*Meeting)) // I would like to log this without popping prom the Queue
    return 0
}

Please see the comment in the code snippet in the minMeetingRooms function.

I would like to log the top of the Priority Queue, without actually popping it. How can I go that?

Banditry

just get the last element of the internal array (define a Peek() function) – Softener

@Softener as per the github code heap.Pop does swapping and percolating before it returns the Pop element. Will the last element always contain the items which heap.Pop will return? – Banditry

@Softener I tried returning the last element but it didn't give me the same one – Banditry

github.com/golang/go/issues/17510 the minimum is at index 0, so actually the first element is sufficient – Softener

Answer 1

You can "peek" the element that pop() will return by returning the first element of the underlying array. (i.e. pq[0])

Softener

Then the time complexity will be O(logN). For peek it is expected to beO(1) – Xenogamy

@Xenogamy He means directly returning the 0th element of the underlying array like pq[0], edited to add that tothe answer, – Banditry

Answer 2

fmt.Println(pq[0])

you need to use the first element to peek

Jehol