These are all interesting ideas, but I'm not quite sure if I understand them fully. I'll start with the first idea (the smooth sort-based priority queue), because it's simpler.
Currently in Sodium the approach is like this:
G - directed acyclic graph representing the FRP system
R - set of roots of G, i.e. sinks
S - set of roots (sinks) firing in the current transaction
G_S - sub-graph of G with roots S (firing sinks and all their dependents, transitively)
G_S,A - sub-graph of G_S, containing only vertices that are "active" (unfiltered) in the current transaction
P - a priority queue of vertices waiting to be processed
for s in S:
v = P.pull()
process v according to the operator it represents, \
which includes pushing its dependents to P iff v is "active" \
in the current transaction, i.e. does not filter the event (which \
can happen in the case of Stream.filter or unchanged Cell)
Insertion to a priority queue based on a heap is
O(log(length(P)). All of
G_S,A vertices will be processed, and only them (which is obvious from the algorithm). So the time complexity is
O(size(G_S,A) * log(length(P)). If G is much wider than deeper (I believe that that's a reasonable assumption), then
size(P) is proportional to
size(G_S,A), so complexity of the algorithm is
O(size(G_S,A) * log(size(G_S,A)).
As I understand it, the single and only reason for this approach is not to process the inactive part of
G_S. As I understand it, it's virtually impossible to hold that single optimization without using any kind of priority queue. It changes if you are ready to give up that optimization, though.
Using the most classic topological sorting algorithms will remove the logarithm from the equation, making it
O(size(G_S)). So basically you can choose from linear-logarithmic complexity based on a smaller variable, or linear complexity on a bigger variable.
From your first post (and the title), I conclude that you want to switch heap-based priority queue for smooth sorting. If only insertion complexity changes, how does that not make it
O(size(G_S,A) ^ 2)?