Why are Golang heaps so complicated | Hacker News Reader

Why are Golang heaps so complicated

dolthub.com

91 pointsnalgeon12 comments

For me it’s actually the opposite. I dislike the container/heap functions for the fact that Push() and Pop() try to pass through values in the first place.

Especially for Pop() it’s completely gratuitous. It’s fairly common that you want to peek at the min-element prior to popping. For example, a work queue might only want to pop jobs if their scheduling time exceeds the current wall time. In that case you already need to inspect x[0] by hand. And if you do that, you simply don’t use Pop()’s return value.

I would rather see that the ‘any’ arguments/return values are removed entirely, and that the caller is responsible for reading/writing them from/to the array directly. It’s sufficient for container/heap to just implement the heapify algorithms. Its interface could just be identical to sort.Interface.

Even though some people hate it, I think it’s beautiful that sort.Sort() is implemented in such a way that it’s oblivious of the underlying data structure and element type, I wish container/heap adhered to the same principle.

The advent of generics should enable better container structures - whether they’ll hit the standard library is a different matter I suppose.

For a heap, something like this seems fine? https://pkg.go.dev/github.com/fufuok/utils/generic/heap#sect...

(Hi, Ed!)

Because it comes from a time when the go team was really enamored with using interfaces for logic. c.f. the sort package before the introduction of sort.Slice, where you'd cast your slice to different types to get different sort functions.

It's because the package predates generics and a v2 hasn't been added yet.

I really disliked Go as a language before generics. I was constantly frustrated by the limitations and clunky workarounds; often without code generation what you were trying to accomplish was simply impossible. Go generics are still a little anemic by modern standards but they are such a breath of fresh air.

I’m not super familiar with Go generics, but would it be able to express the kind of constraints you’d typically want for a heap, namely that the elements are comparable in some way?

For built-ins, yes: https://pkg.go.dev/cmp@go1.21.4#Ordered

Custom types would require a custom interface.

I did a slightly different generic implementation of heaps here: https://github.com/addrummond/heap

The main difference is that is that the comparison function is determined from the type of the heap element both for built-in and user-defined types.

    const (
     Break    BreakOrContinue = iota
     Continue BreakOrContinue = iota
    )

This is not how `iota` works...

Amazingly enough, it is (try it yourself!). This predefined identifier changes its value for every constant declaration [1], and the declaration itself just fills the expression list from the previous when missing.

[1] https://go.dev/ref/spec#Iota

Hmm, as the sister comment points out, this sets Break and Continue to different values, which is all that’s required. Maybe there is a more stylish way of accomplishing the same thing that I’m unaware of, but it’s not a bug.

This is a nice example of the bizarre negativity you tend to get when posting any project on an Internet forum. I don’t expect anyone to be even remotely impressed by my implementation of a completely standard binary heap. But it’s amusing that the one comment that this has attracted is a piece of snark that appears not even to be technically correct.

    NameError: name 'heappush' is not defined

Lies, damn lies

Reply on news.ycombinator.com