Design – Why Most Languages Provide Min-Heap Instead of Max-Heap Implementation

There are a few questions to ask when dealing with large quantities of data (I leave "large" intentionally vague).

• Can all of the data fit into memory at once?

• Is the amount of data known up front? Or could more come in while the algorithm is processing?

• Is it feasible to sort the data before analyzing it?

Most college-level exercises tend to deal with small amounts of data, so these questions do not matter. However, consider Google: they have massive amounts of data, and loading the entire search index into memory and sorting it is nowhere near feasible.

Even when the amount of data could fit into memory, sometimes the best solutions are ones that work in the larger case. For example, you may not need to sort this array to find the largest elements. From a theoretical perspective Big-O notation is great: however, in the real world, sometimes the fact that O(n + n log n) simplifies to O(n log n) is not a big reassurance. It could translate into minutes or hours of extra run time.

Big-O analysis:

1. While the link you posted claims it to be O(n), as does Wikipedia, I disagree. Big-O is about worst-case complexity, which is actually O(n²). While the average-case is n (there is no letter for that), the worst-case is a huge time killer.

2. The array is iterated once, which is O(n). Modifying the binary heap is O(log₂ k), but is performed (worst case) n times. This makes the whole thing O(n + n log₂k) = O(n log₂k). Also keep in mind that k is small compared to n, and log₂k is even smaller.

3. Partial selection sort in this instance is O(kn).

The first option may in theory perform well most of the time, with certain data sets performing poorly.

The second option will perform very well all of the time. In the worst case, it is much better than the first algorithm. The first algorithm may outperform this one some of the time, however.

The third option is pretty much constant for a given n: the contents of the array do not matter, only its size.

I would lean toward the binary heap myself, but it might be worth analyzing whether the data would give the Quickselect algorithm a difficult time and perhaps implement both and measure their real-world speed.

For the shortest path, start at the well known Dijkstra's algorithm.

When you're on E, according to certain values and variable states, only G may be available...

A simple solution - which I want to encourage you to implement - is to implement dijkstra such that it calls a function to get the outgoing links from a given node. You can then do your checks there. When the conditions change, you would then invalidate the results of the search, and execute it again.

Note: It is even better if you can mark nodes as invalidated. That way the algorithm can cache the lists of links and only reevaluate for the invalidated nodes.

That a given link or node could be unavailable is not really a problem if the graph cannot change while it is being used. You simply compute it for the graph as you have it.

Since this is a concern, I suppose that there is something that will be traversing the graph and it could find that it changed from one moment to the other... when that happens, this something has advanced some distance on the graph, and it makes sense to compute the path from the current position to the target on the modified graph.

I am not sure how do you want to define longest path...

Perhaps, a good definition for longest path is: the shortest path that maximizes the number of visited nodes. Under that definition, walking an infinite loop is not beneficial.

We would searching for the shortest path... but we need a new metric to call "distance". My initial intuition is to use a metric that does not increase when we visit a new node.

If the distance does not increase nor decrease when visiting a new node, then the following paths are the same length:

A -> B
A -> C -> F -> G -> I -> B

However, we want the second path to be better (I mean, "shorter", I mean, to have a lower value in the metric, I mean, to be preferible).

A simple solution is to decrease the metric when visiting a new node.

Notes:

• A negative metric can be problematic. For path finding, it is not safe to use Dijkstra with negatives. We can normalize it to only positive values by using a sigmoid function before comparing.
• We also need to encode the rule that distance is different depending on whatever or not we have visited a node. You can solve this by similar means to what I described for having parts of the graph unavailable. Except, instead of passing the current node to evaluate the available links, you pass the current path.

With this metric we have:

A B - length: -1

A C D F G I B - length: -6

A C D E G I B - length: -6

A C D E B - length: -4

A C D E J - length: -4

A C D E C D F G I B - length: -5
        ¯ ¯
A C D E C D E G I B - length: -3
        ¯ ¯ ¯
A C D E C D E B - length: -1
        ¯ ¯ ¯
A C D E C D E J - length: -1
        ¯ ¯ ¯
A C D E C D E C D E F G I B - length: -1
        ¯ ¯ ¯ ¯ ¯ ¯

Then our "longest" path is one of the two longer paths that does not loop (A C D F G I B or A C D E G I B).

In case it is not evident, a path with a loop is always considered worse than its variant without loops because the loop traverses visited nodes, and thus increases the metric. And remeber that we are minizming the metric.

If you are using Dijkstra with a sigmoid of this metric - as I suggest - the loops will be discarded because - as explained above - they will always yield worst paths that those without loop.

Addendum: After posting the answer, I notice that I got some interesting results... for instance: A C D E C D F G I B manages to visit more nodes than A C D F G I B but scores worse (higher), that is not what I expected. I suppose we can tweak it to be more or less interested in going out of its way to reach more nodes before going to the target by applying factors to the added or decreased distance... for example, we could increase only half the value when traversing a visited node. What is the ideal proportion to increase? I have no idea. For practical purposes it can be tweaked to suit the design or problem domain.