12 ms·

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 seman

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) https://en.wikipedia.org/wiki/Heap_(data_structure)

ajross 8y ago
> 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.
- banachtarski 8y ago
  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.
  - dev_dull 8y ago
    Sounds like their would be mutual filtering.
- gcb0 8y ago
  sounds like all those people are filtering for is who went to the same university, at around the same time as they did.
  - stochastic_monk 8y ago
    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.
    - jdlyga 8y ago
      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.
    - ajross 8y ago
      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.
      - stochastic_monk 8y ago
        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.
- jdlyga 8y ago
  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.
- justin66 8y ago
  > 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?
  - ajross 8y ago
    Why would one even need such a term? The difference is the direction of the pointy end in the comparison operator...
    - justin66 8y ago
      > 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.
sdegutis 8y ago
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?
- AstralStorm 8y ago
  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.
  - jstimpfle 8y ago
    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.
    - AstralStorm 8y ago
      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.
      - kadoban 8y ago
        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.
ItsMe000001 8y ago
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.
- OskarS 8y ago
  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.
  - ItsMe000001 8y ago
    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.
jki275 8y ago
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.
- isaachier 8y ago
  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.

ajross 8y ago

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

banachtarski 8y ago
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.
- dev_dull 8y ago
  Sounds like their would be mutual filtering.
gcb0 8y ago
sounds like all those people are filtering for is who went to the same university, at around the same time as they did.
- stochastic_monk 8y ago
  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.
  - jdlyga 8y ago
    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.
  - ajross 8y ago
    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.
    - stochastic_monk 8y ago
      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.
jdlyga 8y ago
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.
justin66 8y ago
> 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?
- ajross 8y ago
  Why would one even need such a term? The difference is the direction of the pointy end in the comparison operator...
  - justin66 8y ago
    > 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.

sdegutis 8y ago

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?

AstralStorm 8y ago
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.
- jstimpfle 8y ago
  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.
  - AstralStorm 8y ago
    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.
    - kadoban 8y ago
      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.

ItsMe000001 8y ago

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.

OskarS 8y ago
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.
- ItsMe000001 8y ago
  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.

jki275 8y ago

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.

isaachier 8y ago
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.