Hacker News Reader

Comment by flafla2 | Hacker News Reader

A "max heap" is a heap that has O(1) access of the maximum priority element, as opposed to a "min heap" which returns the lowest priority. It's largely a semantic distinction, as a max heap = a min heap with negative keys. Also a heap isn't just a packed tree, it's referring specifically to a heap data structure [1] (which is often implemented using a packed tree, but not necessarily).

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)

View on HN

> I'd expect any CS grad past an sophomore undergraduate level to understand exactly what a max heap is

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.

Surely you've heard the distinction between the max-heap and a min-heap before...

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.

Sounds like their would be mutual filtering.

sounds like all those people are filtering for is who went to the same university, at around the same time as they did.

I don’t think so. Heaps are a bread-and-butter data structure typically covered in an undergraduate Data Structures course and then used in an undergraduate introductory Algorithms course.

I’d expect someone to know heaps the same way I’d expect them to know about hashmaps or quicksort.

True, but so many excellent programmers, people with 10 years of experience, typically don't remember all the details of classes they took a decade ago. I remember heaps, but I'd have to look up the details since it's not something I work with everyday. Once you're deep into your career, it's much more about practical real world style programming.

But as mentioned multiple times, I do know heaps. I've written heaps that were deployed in production software even. Yet given a question that asks without context "Write a max heap" I'd be lost. That's not a term I know.

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.

I agree that the list isn’t good. I would only expect someone to know that it permits constant time access to a maximum or minimum element, and that it has a tree structure. Actually writing an implementation I would not.

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.

Totally agree. You learn so much theory in computer science courses, but that is less important during practical career work. It's much more about learning codebases, libraries, and good debugging skills.

> I've written several heap-based priority queues over the course of more than two decades of professional work

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?

Why would one even need such a term? The difference is the direction of the pointy end in the comparison operator...

> Why would one even need such a term?

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.

I've had a BSCS for years, an MS in a related field and working on an MSCS and I've never heard of "max heap" or "min heap".

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 just don't understand how this is possible. The only way to implement Dijkstra's algorithm in less than O(|V|^2) time is using a min-heap. In practice it might be rare to use heaps over ordered sets but it is one of the first tree structures I was taught in my data structures course.

This is the first time ever I hear about "max heap", or quite possibly I heard it and promptly forgot it. No, I don't accept your implication about my credentials and how I fared in practice since getting the degree in 1997 supports me (it's quite algorithm-heavy for the last few years). Some people take their own favorite subjects waaayyyyy too seriously.

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.

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.

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.

You are not saying anything that I did not already respond to. I know trees, I know priority queues, I completely understand the data structure. What's the point of being able to assign some completely made-up and arbitrary name to it? If you think being a walking lexicon is an achievement, okay. That's spelling contest kind of "knowledge". I get it - some people really like it. Everybody is different and that is fine. Names (by themselves) mean a lot to many people. It's a low-effort signaling thing I guess. It is fine if I was ever selected against in such an interview - it would be entirely mutual. I do not believe it tests what you think it does. If you need a priority queue and don't happen to be able to come up with a good data structure on your own - or if you are too lazy to think about it - you can just google it. As long as you understand the basics of the underlying data structures - trees, arrays, lists, graphs (in general) - you easily understand the nuances of the particular variation of the base structure.

Heaps are not exactly obscure datastuctures and they are practically useful. They are also relativity simple to implement. I wouldn't ask about them in an interview, but wouldn't be surprised if I were asked.

I don't understand the purpose of your reply. You built a straw man which you now attack. I didn't say "data structures don't matter" or whatever else you interpret into my comment. Also read my other reply to another reply.

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.

From your previous comment:

> 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.

Why are you being so nasty?

> 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.

http://dilbert.com/strip/2015-06-07

I do agree we have a 'dick from the internet issue here'.

Hello Dick, oh so you found a mirror, great! I doubt self-reflection is something a troll like you is capable of though, given that your ability to parse simple English without self-projecting your own - pretty limited and frankly a bit stupid - thoughts into other people's content. That's some narcissism component that you have here.

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!

I've had dozens of interviews for mid-level and senior-level engineer positions in the past 10 months at many diverse companies and gotten offers from most of them (retracted for unrelated reasons), and none of them asked about data structures even close to this. So it seems like it's probably really obscure. Or maybe only interviews for certain positions look for this kind of knowledge?

Almost nobody writes heaps anymore, they're not even the best structure for priority queues now, that typically taken by skiplists or more advanced balanced trees like red-black tree.

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.

I'm curious, what's wrong with array based heaps? I've implemented both Red-black trees and array based heaps in the past. If I had to take a guess I would say the latter should be noticeably faster. In any case Red-black trees are much harder to implement.

The problem with heaps is cache locality if you have anything different from tiny types like pointers stored inside. Plus that they do have to be resized more often than the other structures and you're forced to allocate a continuous chunk of memory if they're big. (And for small, you actually cannot beat a simple list with a one item sort by a heap.)

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.

Red-black trees aren't known for having good spatial locality of reference (heaps aren't either, but I fail to see how this is a point in favor of RB trees). Is there a particular implementation that doesn't share this shortcoming that you had in mind? That would be interesting to me.

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.

I was wondering the same, and was thinking that maybe the RB needs to touch fewer nodes to rebalance after a remove operaiton, thus resulting in better cache friendliness (although GP said cache _locality_)? But it seems unlikely since the heap property is much weaker than the RB-balanced binary tree property.

RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage and are not moved far around as in some balancing trees and are small. Thus you end up with cache locality even when not directly aiming at it.

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.

> RB tree nodes abuse the interesting and common property that nodes are created next to each other most of the time in typical usage

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.

A heap tree has a very specific structure, even if value locations have some flexibility. An RB-tree has more flexibility in its structure, with rigidity in value locations.

If cache locality is a big concern, you should either think about implementing some variation of a B-tree, or do very fancy things like design trees with van Emde Boas layouts (which are cache oblivious and thus has excellent cache performance) [0]. Or both, at once!

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.

[0]: http://tildeweb.au.dk/au121/papers/soda02.pdf

Yes, if you're keeping pointers. The thing is, the gain is completely wiped out by maintaining the heap invariant which has to copy the whole thing instead of walking a single branch. The same memory bandwidth issue plagues B trees. This shows up with big trees. For small, again, you're better off with a list.

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.

PHK's "B-heaps" are interesting: https://queue.acm.org/detail.cfm?id=1814327 .

Cool startups that want to be like Google and FB, but are still at around 10 employees.

Reply on news.ycombinator.com