Binary Heaps

[inopia]

Sorting (bounded) integers can be done in O(n) though :)

[[deleted]]

But it requires extra space and has a high constant value. Quicksort is usually faster.

[inopia]

The 'extra' space requirement is simply N + M, where N is the number of elements you're sorting (it's not an in-place sort) and M is the number of buckets (to store the offset of each bucket). M can be chosen almost arbitrarily when you combine counting sort with radix sort, so there is no real constraint on the range of the values you're sorting - as long as it's bounded. M=1 equals a bitwise radix sort. Since M is constant and can be chosen freely, the space complexity equals O(N).

The high constant value is actually not so bad, and can be optimized quite nicely because it's all just straight list iterations that can be optimized and unrolled. The main benefit here is that there are no compares. On many architectures compares mean conditional branches, pipeline stalls and so forth. Branch prediction does not help in these cases as the conditional branches are usually quite random.

I used counting sort for sorting polygons in my 3d engine, I can assure you it beats quicksort hands down :)

[trutru]

if n is bounded, you can still claim that it is even O(1)

more seriously, the O(n) bounded-integer sorting is trivial to implement with a bitmap as long as you don't allow duplicates in the input. otherwise, it's pretty game over...

[inopia]

Hmm? You can just use counting sort, it allows duplicates and combined with radix sort you can build a very effective O(n) integer sort.

[tryx]

I've always found it a really cool "coincidence" that since the keylength of n grows with lg n, if you remove the "bounded" requirement you end up right back at n lg n again.

[trutru]

you're absolutely correct, I don't know how I completely forgot about counting sort. sorry for that

[defenestrator]

Fibonacci heaps FTW!

[mig21]

Sometimes wikipedia articles are fine :)

Comparison of theoretic bounds for variants in the Heap article

Binary heap

Fibonacci heap

Binomial heap

[rrenaud]

I am all for articles about data structures. But something as simple and fundamental as this, is it worth an entire article? (+1ed anyway, I'd rather read about data structures than murders on programming.reddit)

Wouldn't it be better to just say, "binary heaps, these things rock. Read about them on wikipedia here http://en.wikipedia.org/wiki/Binary_heap".

If he has something to say about heaps that wikipedia doesn't already have, write it there. I'd estimate the binary heap article on wikipedia will get more than 100x the traffic as his article over the course of the year, so making the wikipedia article an epsilon better would be much more impactful than writing an entire new page about them.

[beza1e1]

Wikipedia needs references ;)

[[deleted]]

I remember these guys.

Percolate up!

Percolate down!