0
$\begingroup$

So in my "Advanced algorithms" course, we were taught about the "self-organizing list" data structure. The professor showed the following three heuristic algorithms: Frequency Count, Move to Front and Transpose.

Looking online, I could not find any other "popular", "common" or "used" heuristic algorithms. Are there any other heuristic algorithms that the self-organizing list can implement (without knowing the distribution of the input)? What are their benefits?

$\endgroup$

2 Answers 2

0
$\begingroup$

You can check these two surveys for discussions of other heuristics like TIMESTAMP and MRI, beyond the 3 common heuristics:

$\endgroup$
0
$\begingroup$

There are two situations. One, you want a list organised so that the most requested items are at the front of the list and found quickest. In that situation you will more likely use a hash which gives you fast access to all items (and finds equally fast that an item is not present, which a linked list cannot do).

The other situation is that you want items in a rough order of importance. In that case you might use a priority queue instead.

From a programming point of view, the implementation will often be hidden from you. You use an abstract data structure, you know what features it offers, but you wouldn’t even know if it is a linked list, a hash map, or for very small numbers of items even an array.

(I had a situation where I needed many many thousands of lists. But many lists were empty, 90% contained just one item, and the others had few. So I created a class with a pointer that could be null, point to the single item, or to a small array of items - providing the full interface for a linked list. )

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.