4 ms·

Why are Golang heaps so complicated

91 points by nalgeon 3y ago

EdSchouten 3y ago
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.
- jen20 3y ago
  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#section-readme https://pkg.go.dev/github.com/fufuok/utils/generic/heap#sect... (Hi, Ed!)
saagarjha 3y ago
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?
- tommiegannert 3y ago
  For built-ins, yes: https://pkg.go.dev/cmp@go1.21.4#Ordered https://pkg.go.dev/cmp@go1.21.4#Ordered Custom types would require a custom interface.
icholy 3y ago
It's because the package predates generics and a v2 hasn't been added yet.
- DangitBobby 3y ago
  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.
foldr 3y ago
I did a slightly different generic implementation of heaps here: https://github.com/addrummond/heap 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.
- kiitos 3y ago
  const ( Break BreakOrContinue = iota Continue BreakOrContinue = iota ) This is not how `iota` works...
  - lifthrasiir 3y ago
    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 https://go.dev/ref/spec#Iota
    - deleted 3y ago
      [deleted]
  - foldr 3y ago
    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.
tedunangst 3y ago
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.
nilslindemann 3y ago
NameError: name 'heappush' is not defined Lies, damn lies

91 points by nalgeon 3y ago

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.

jen20 3y ago
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#section-readme https://pkg.go.dev/github.com/fufuok/utils/generic/heap#sect... (Hi, Ed!)

saagarjha 3y ago

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?

tommiegannert 3y ago
For built-ins, yes: https://pkg.go.dev/cmp@go1.21.4#Ordered https://pkg.go.dev/cmp@go1.21.4#Ordered Custom types would require a custom interface.

icholy 3y ago

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

DangitBobby 3y ago
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.

foldr 3y ago

I did a slightly different generic implementation of heaps here: https://github.com/addrummond/heap 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.

kiitos 3y ago
const ( Break BreakOrContinue = iota Continue BreakOrContinue = iota ) This is not how `iota` works...
- lifthrasiir 3y ago
  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 https://go.dev/ref/spec#Iota
  - deleted 3y ago
    [deleted]
- foldr 3y ago
  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.

tedunangst 3y ago

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.

nilslindemann 3y ago

NameError: name 'heappush' is not defined Lies, damn lies