...OK, actually I can only think of 2 things to use a Min Heap for:

1. A heap sort.

2. Building Huffman trees.

Can anybody else think of a good use for a Min Heap? (Or even a Max Heap?)

I can think of plenty of algorithms that require some data in sorted 
order, but any sorting algorithm will do for that. (And on current 
hardware, in-place algorithms are usually faster than a heap sort.) Can 
anybody think of an algorithm that benefits from an actual heap?



[For anybody not already familiar with such things...

A Min Heap is a kind of binary tree that stores data in such a way that 
retrieving the "minimum" element is an O(1) operation. Insertion and 
deletion are both O(log n), and I believe joining two heaps should be 
O(log n) as well.

A "heap sort" involves turning something into a heap (with O(n log n) 
complexity) and then repeatedly removing the minimum element (with O(n) 
complexity) to yield a fully sorted list.

To build a "Huffman tree", you start with a set of trivial 1-node trees. 
Each tree has a probability assigned to it. The algorithm is to simply 
select the two lowest-probability tries, remove them from the set, 
combine them into a larger tree (with a correspondingly higher 
probability) and insert this back into the set. Eventually you will have 
1 tree with Pr=1.

If this "set" is in fact a Min Heap sorted by tree porbability, then you 
end up with a nice fast algorithm.

Here ends the lesson on algorithms and data structures.]

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message