Never once heard the term, and I've written several heap-based priority queues over the course of more than two decades of professional work.
So... yeah, I'm too dumb for that filter I guess.
And honestly, I'm sure if you asked what it was in an interview, you would get a straight answer and not be dinged for it. I would filter based on your saltiness level though.
I’d expect someone to know heaps the same way I’d expect them to know about hashmaps or quicksort.
Conflation of terminology (about which heaps are already a terribly confusing example) with expertise is kinda the essence of why this kind of list is garbage.
And in any case, I retreat the broader point that has nothing to do with my personal vocabulary: the question wasn't even asking about how heaps work! It just wanted to know you could write a class declaration with the API.
A class declaration with an API (and no implementation) would be rather simple: insert, top, remove, and a constructor.
I will say that I typically hear “heap” and whether it’s max or min is largely implicit in the task, so perhaps the comparator qualification is unneeded.
Out of curiosity, what terminology would you use to distinguish between a heap that offers up the lowest value first and one that offers the highest value first?
Like any word, it's shorthand for a longer set of words.
> The difference is the direction of the pointy end in the comparison operator...
That's not descriptive of what the thing is, that's descriptive of how one part of it will be implemented.
I get that you don't think it is important, but I am surprised that you are acting defensive about the fact that it's a term practitioners ordinarily use. It's the first thing someone who looks up a binary heap is likely to see in Wikipedia, captioning the top two illustrations in that article. It's not just Stanford-cult algorithmic knowledge.
Your explanation makes it quite clear and I guess now I know -- but it's not been common in anything I've ever seen.
I have no intention of becoming or finding good becoming a walking lexicon of obscure algorithms and minutiae. Thank god I'm really good at forgetting stuff I don't need - as well as learning stuff I do need but never did before, but only when I actually need it. Dynamic learning capability (let's just call it that) seems far superior to me than static learning. We have Google to outsource a lot of that to.
Anyway, looking up max heap it's trivial, no idea what my benefit would be if I knew every variation of a tree structure somebody came up with by heart. Often it's just a name for something that anyone who needs it would come up with by themselves anyway if they understand the greater concept because it's kind of obvious. I have used plenty of data structures for which I'm sure someone invented a name for without knowing that name.
It's not just any other tree structure. It's the tree structure that is by far the most common way of implementing a priority queue, and it's the tree structure at the heart of the algorithm "heap sort", which is not exactly obscure. It's also the tree structure that gives "the heap" its name (though modern operating systems and allocators don't use heaps for this purpose anymore). I've personally implemented heaps in a variety of languages and contexts throughout the years as part of my work.
I don't want to sound too dismissive here, but this is not some obscure data structure with only theoretical interest. It's perfectly fine to not know off the top of your head what splay trees, Fibonacci trees or skip lists are or how they work. But if you have a degree in computer science, you should know what a heap is.
I understand that it is highly unpopular that some particular knowledge is unnecessary - for every piece of knowledge there are people who feel very strongly about it. I guess that's partly because getting the knowledge was quite an effort, and then psychology kicks in, what was hard to obtain has value by that proxy. Makes it hard to talk rationally and calmly about what is actually needed. That's why questions such as what children or students need to learn are so hard, the discussion always becomes extremely heated, and removing anything from the list can only be done against lots of screaming. So sure, me saying that being able to immediately connect some name and immediately have the respective thing, here some algorithm, available without looking it up is not popular maybe not with everybody, but those who are opposed to what I see feel very strongly about it. Unfortunately that includes interpreting things into what I say/write that is not really there. I mean, obviously, a good and thorough education in algorithm fundamentals is extremely valuable.
> I have no intention of becoming or finding good becoming a walking lexicon of obscure algorithms and minutiae.
This implies that you think that heaps are obscure and minutiae. If that wasn't what you meant I'm not sure why you brought it up in a discussion about heaps.
> I understand that it is highly unpopular that some particular knowledge is unnecessary -
what is highly popular today is the idea that knowledge is unnecessary because you can always google it. You can't google what you do not know it exist.
> This implies
Why don't you stick to what I wrote? You respond to the straw man your own imagination creates.
> is the idea that knowledge is unnecessary
See above. You are being quite ridiculous.
EDIT: I knew it, you narcissist use alt accounts for voting manipulation. LOL, I won't even report you, sick little child (no sane person would go through such trouble for literally nothing). I knew it was only you all along, and this comment was a provocation test - nobody else is reading this any more at this point. The only way to get such a quick within-minutes reaction to this comment is if you cheat (and use a notification service, which was already likely in your case so I counted on it). Got you! My own personal troll, I feel honored!
It is one of those stupid questions. The good question would be to task them to implement a priority queue (also a bit rough as they are in standard library now or boost, but for old C++ you may get to write one) and see what they come up with. Discuss a bit too.
Both skiplists and rbtrees allow for a tricky but efficient colored pointer implementation and also if you need fine grained locking or lock free implementations.
If allocating a heap as a big chunk were a problem, you could certainly do it as nodes and pointers like a RB tree is traditionally done (reify the tree instead of array-encode it). Though the array-encoding is itself usually an optimization, so I wouldn't think you'd want to do that. Doing one big allocation (and copy) every once in a while (in a table-doubling-esque manner) should be a win over individually allocating nodes, if you can amortize over many operations. And again if that's not true or undesireable, you can just allocate a heap like you'd allocate a tree normally.
Both of these things are significantly more complex than just implementing a simple max-heap, which will almost certainly perform well enough for most any practical purpose. A red-black tree will probably have significantly worse cache behaviour than a max heap, since every dereference is jumping around in memory. In a max-heap, you can count on having at least a couple of the first levels in cache when you start.
Van Emde Boas trees are better but yet more complex still. (And colored pointer variant is not available for them)
The tradeoff is speed of write vs read in case of heaps. They have pretty bad write performance.
B+trees have some of that property by only keeping data in leaves, but you need a very smart leaf layer to capitalize on it. You end up with more inner nodes though.
That's true only if you create the nodes in already sorted order. Furthermore, for the RB version of priority queues, you need pointers, which are not needed for the array based variant (the childs of cell x are always 2* x and 2* x+1), which typically adds another 16 bytes of data per node.
This is very common terminology, and honestly I'd expect any CS grad past an sophomore undergraduate level to understand exactly what a max heap is, especially in an interview setting.
[1] https://en.wikipedia.org/wiki/Heap_(data_structure)