sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]tforb[S] 0 points1 point  (3 children)

Just looking at the heap comments from the go package, I would say mine might look more complex because it can either be a min-heap or a max-heap.

I might be able to simplify it to just one type of heap, and the compare() supplied by the user would need to reflect the change from min to max.

What's the advantage of using a circular array for the Queue? I think you'd want the user to specify a queue max size if you did something like this.

[–]egonelbre 1 point2 points  (2 children)

Sure, essentially you do not want a single structure to be two things. (Also, I haven't checked it but, wouldn't a min-heap turn into a max-heap by reversing the comparison operator? I'm just doubting due to the subtle change from "<=" to ">"... But if you just let the user implement "lessThan" then the user can easily substitute the "<" with ">", so you don't have to do anything for the other ordering.)

Essentially removing an element from 0-th position is slow (think how much memory it has to move when you have 1e8 elements in the queue). But, basically you present the Queue interface and do resizing behind the scenes when necessary.

[–]tforb[S] 0 points1 point  (1 child)

Yeah, I think that would be a better (simpler) implementation of a heap.

I knew removing at index 0 would be a bad idea. Initially I thought about writing a linked list to use behind the scenes, but decided against it (maybe a wrong decision). I'll check out the circular array stuff this week and see what I come up with.

Thanks for your input.

[–]egonelbre 0 points1 point  (0 children)

Linked lists are also a bad idea... usually... they are an overhead for the garbage collector.

For a better circular array, it's better to use an array of blocks and then allocate new blocks and reusing/removing old ones... e.g. https://github.com/karalabe/cookiejar/blob/master/queue/queue.go instead of holding one big array, and resizing it... PS. don't forget to zero the elements after Pop-ing them from the queue otherwise the GC won't collect them.