In Go's container/heap, which five methods must your type implement?
answer
- it does not start from scratch
- one familiar ordering contract, embedded
- two more, and both change the length
- append at the end, detach from the end
basics
~20 scontainer/heap.Interface embeds sort.Interface, so your type needs Len, Less and Swap, plus Push(x any) to append one element and Pop() any to remove and return the last one. Five methods, and you own the storage.
solid answer
~40 s`heap.Interface` embeds `sort.Interface`, so you supply `Len() int`, `Less(i, j int) bool` and `Swap(i, j int)`, and on top of those `Push(x any)` and `Pop() any`. Those last two are pure storage operations: `Push` appends the element at the end, `Pop` removes and returns the element at index `Len()-1`. The package supplies the algorithm — `heap.Init`, `heap.Push`, `heap.Pop`, `heap.Fix` and `heap.Remove` call your `Less` and `Swap` to sift elements into place. `Less` defines a min-heap: whatever `Less` ranks first ends up at index 0, so a scheduler that orders by `Deadline.Before` gets the earliest job at the root. `Push` and `Pop` change the slice length, so they need a pointer receiver, which means you pass `&q` to the package functions.
code
go · 33 linestype Job struct {
Name string
Deadline time.Time
index int
}
type JobQueue []*Job
func (q JobQueue) Len() int { return len(q) }
func (q JobQueue) Less(i, j int) bool { return q[i].Deadline.Before(q[j].Deadline) }
func (q JobQueue) Swap(i, j int) {
q[i], q[j] = q[j], q[i]
q[i].index = i
q[j].index = j
}
func (q *JobQueue) Push(x any) {
job := x.(*Job)
job.index = len(*q)
*q = append(*q, job)
}
func (q *JobQueue) Pop() any {
old := *q
n := len(old)
job := old[n-1]
old[n-1] = nil // release the pointer left in the spare capacity
job.index = -1
*q = old[:n-1]
return job
}go deeper
Be ready to name all five methods and say which three come from sort.Interface. Knowing that Push appends at the end and Pop detaches the end is enough to pass this rung.
Explain who does what: your methods are storage, the package functions do the sifting. Expect to say why Push and Pop need a pointer receiver and why only the pointer type satisfies heap.Interface.
Show that you would wrap this in a small type rather than scatter heap.Push calls through a daemon, and that you keep the heap invariant testable. Mention heap.Init on a pre-filled slice and the nil-out inside Pop.
Frame the tradeoff: five hand-written methods and an any-typed Push against writing or importing a typed queue. Argue when a hand-rolled heap in the standard library beats a dependency for a team that has to maintain it.
## container/heap is an algorithm, not a container Despite the name, `container/heap` stores nothing. It is a handful of free functions that operate on storage **you** declare, reached through one interface. That is why the package can heap-order a slice of job pointers, a slice of ints, or a ring buffer you wrote yourself — it never needs to know. The contract: ``` type Interface interface { sort.Interface // Len() int; Less(i, j int) bool; Swap(i, j int) Push(x any) // add x as element Len() Pop() any // remove and return element Len() - 1 } ``` ### The three inherited from sort.Interface - **`Len() int`** — how many elements are currently in the queue. For a slice type this is `len(q)`. - **`Less(i, j int) bool`** — reports whether the element at `i` should rank ahead of the one at `j`. This single method decides the whole ordering. `container/heap` builds a **min-heap** with respect to `Less`, so the element that no other element is `Less` than sits at index 0. Want a max-heap? Invert the comparison inside `Less`; there is no flag for it. - **`Swap(i, j int)`** — exchange two elements. The package calls this constantly while sifting, and if your items carry a position field, this is the one method that must write it back. ### The two the heap adds - **`Push(x any)`** — append `x` as the new last element. That is all. It must *not* try to place the element in order; `heap.Push` sifts it up afterwards. - **`Pop() any`** — remove and return the element at index `Len()-1`. Again, that is all. It must *not* return the smallest element; `heap.Pop` first swaps the root down to the end, restores the invariant, and only then calls your `Pop` to detach it. The two names are the classic trap. `q.Push` and `q.Pop` are the *storage* half; `heap.Push(&q, x)` and `heap.Pop(&q)` are the *heap* half. Calling the methods directly compiles fine and quietly gives you a plain stack. ### The package functions you actually call - `heap.Init(h)` — establish the invariant over an already-filled slice, O(n). - `heap.Push(h, x)` — your `Push`, then sift the new last element up. O(log n). - `heap.Pop(h)` — swap index 0 with the last element, sift down, then your `Pop`. O(log n). - `heap.Fix(h, i)` — restore ordering after the element at `i` changed value. O(log n). - `heap.Remove(h, i)` — pull the element at `i` out of the middle. O(log n). Every one of them takes a `heap.Interface`, so you pass `&q`, not `q`. ### Receivers `Push` and `Pop` change the slice's length, so they must be declared on a pointer receiver — a value receiver would append to a copy of the slice header and the caller would never see the growth. `Len`, `Less` and `Swap` can stay on a value receiver, because they read the length or write through the backing array that the copy shares. Mixing receivers like that is legal and is exactly what the standard library's own example does. The consequence is that only `*JobQueue` has all five methods in its method set, so only `*JobQueue` satisfies `heap.Interface`. ### Why five methods instead of a generic type `container/heap` predates generics, so `Push` and `Pop` traffic in `any` and you type-assert on the way out (`heap.Pop(&q).(*Job)`). The upside of the interface shape is that the heap does not own your backing store: you can index into it, walk it in a test, keep a position field on each element, or reuse the same slice for something else once the queue drains. ### The shape in practice A delayed-job scheduler keeps `[]*Job` ordered by deadline. `Less` compares `Deadline`, `Swap` exchanges the pointers, `Push` appends one, `Pop` detaches the last. The daemon calls `heap.Push` when a job arrives and `heap.Pop` when the root's deadline has passed. Nothing else in the program has to know how a heap works.
- Which element ends up at index 0, and how do you get a max-heap instead?`container/heap` builds a min-heap with respect to your `Less`: index 0 holds the element that no other element is `Less` than. There is no max-heap switch — you invert the comparison inside `Less`, for example returning `q[i].Deadline.After(q[j].Deadline)`, and the latest deadline becomes the root.
- Why does heap.Init exist if you could just push every element one at a time?`heap.Init` establishes the invariant over a slice you already filled, in O(n), whereas n calls to `heap.Push` cost O(n log n). It is also mandatory rather than merely faster: if you built the slice by appending directly, the invariant does not hold and `heap.Pop` will hand back the wrong element until you call `heap.Init`.
- Can Len, Less and Swap use a value receiver while Push and Pop use a pointer receiver?Yes, and that is the standard pattern. Mixed receivers are legal; the only consequence is that all five methods land in `*JobQueue`'s method set and just three land in `JobQueue`'s, so `*JobQueue` is the type that satisfies `heap.Interface` and `&q` is what you pass to the package functions.
The package is a librarian who reshelves, not a shelf. You provide the shelf, a way to count it, a way to compare two books and a way to swap two slots; the librarian does the walking.
saying these in an interview costs you the question
- Says heap.Interface only needs Push and Pop
- Thinks the package keeps the slice fully sorted
- Believes the Pop method must return the smallest element
- Assumes container/heap gives a max-heap by default
- Forgets that Less alone defines the ordering