[HN Gopher] Why are Golang heaps so complicated
       ___________________________________________________________________
        
       Why are Golang heaps so complicated
        
       Author : nalgeon
       Score  : 70 points
       Date   : 2023-12-01 23:26 UTC (23 hours ago)
        
 (HTM) web link (www.dolthub.com)
 (TXT) w3m dump (www.dolthub.com)
        
       | EdSchouten wrote:
       | 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 wrote:
         | 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!)
        
       | saagarjha wrote:
       | 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 wrote:
         | For built-ins, yes: https://pkg.go.dev/cmp@go1.21.4#Ordered
         | 
         | Custom types would require a custom interface.
        
       | icholy wrote:
       | It's because the package predates generics and a v2 hasn't been
       | added yet.
        
         | DangitBobby wrote:
         | 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 wrote:
       | 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.
        
       | tedunangst wrote:
       | 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.
        
       ___________________________________________________________________
       (page generated 2023-12-02 23:00 UTC)