Hacker News Reader

Comment by malisper | Hacker News Reader

There's a specific reason I didn't mention priority queues in the post. In most cases, anything you can do with a heap you can do with a binary tree instead! A binary tree has O(log(n)) insert and deletion which is the same as a traditional heap. The only advantage a traditional heap has is you can construct a heap in O(n) time whereas a binary tree takes O(nlog(n)) time.

Of course there are even more niche data structures like a Fibonacci heap which have O(1) insertion, but you will have to get extremely unlucky to get asked about a Fibonacci heap in an interview.

View on HN

One more thing: a heap can be easily packed contiguously in memory, while the tree nodes are typically dynamically allocated.

This helps with allocation pressure, which is often the "hidden" cost people don't pay enough attention to, especially in garbage-collected languages where the allocation might appear to be almost "free" (often a simple bump allocator), but the deallocation price is paid at later indeterminate time (when the GC runs).

But heap gives you O(1) max/min and Binary tree gives you O(log(n)) of max/min. Am I wrong?

In C++ (for example) getting the minimum and maximum is an O(1) operation [1][2]. I guess this is probably enabled through some extra bookkeeping and many other languages may do the same.

[1]: https://en.cppreference.com/w/cpp/container/set/begin

[2]: https://en.cppreference.com/w/cpp/container/set/rbegin

Wouldn't that mean you have to implement the binary tree as part of your solution?

Seems way easier/time efficient to just use the built-in heap/priority queue of the language standard lib

C++ has built in binary trees with fast iteration. The C++ binary tree is my favourite standard library data structure of any language I've used, it isn't the fastest out there but it has so many useful things you can do with it. You can use it as a heap, you can use it as a dictionary, you can use it to sort things, you can insert items at the same time you iterate through it and if they are after where you are in the tree then you will find them in your iteration etc. It does so many things right that others don't do, I'm sure the others data structures are slightly faster but the C++ binary tree is so powerful and still fast enough for basically every problem.

Oh interesting, I'll have to try that, didn't know there was a built-in one

A priority queue is the easy answer to virtually any “top k” problem so is still worth mentioning.

That's reasonable, makes a lot of sense.

Reply on news.ycombinator.com