This post is targeted to people who develop G’MIC filters. It probably won’t be very interesting for others
Today, I’ve added two new functions to the G’MIC maths evaluator, which allow developers to work with minheap structures. Minheaps are useful structure for modeling priority queues. In G’MIC, they are stored as dynamic arrays
.
The new functions are:

da_push_heap(_#ind,elt1,_elt2,...,_eltN)
: Insert theN
given elements in the minheap#ind
. 
da_pop_heap(_#ind)
: Remove and return the min element from the minheap.
They basically act like the already existing functions da_push()
and da_pop()
, except that they ensure the dynamic array keep a minheap structure, meaning the value at position [0]
is always minimal. And each has a quite nice algorithm complexity of O(log(N))
, where N
is the number of element in your heap.
An example is worth 1000 words:
foo :
1x2 # [0] and [1] are two dynamic arrays (initially empty). [1] will be used as a minheap.
eval "
const N = 300; # Number of values to push
# Push random values in minheap [1].
repeat (N,
value = round(u(100));
da_push_heap(#1,value);
);
# Pop values from minheap [1] and insert them in dynamic array [0].
# > As the pop_heap() function always return the minimal value in the minheap [1],
# you'll end up with a sorted array.
repeat (N,
elt = da_pop_heap(#1);
da_push(#0,elt);
);
"
rm. da_freeze
plot # Plot sequence of values in dynamic array [0].
which gives:
I hear you saying: “Hey! but I could use the sort
command, after pushing all those values to get the same result!”. That’s true, but that was a toy example to illustrate the property of minheaps
Now, another use case, where minheaps can be useful : Suppose you have a set of random points and you want to draw, for each point, the Kclosest connections with the other points.
That’s simple: For each point, just compute all the distances to the other points, and push them in your minheap. Then, pop only K values, and you’ll get it :
foo : check "isint(${1=3}) && $1>=0"
# Generate a list of random points (but wih a minimal distance between them).
# [0]: list of points (random xy coordinates)
srand 0
600,600 noise_poissondisk. 50 1,1,1,2 eval.. "i?da_push([x,y])" da_freeze. rm..
# [1]: matrix of distances between all pairs of points.
{0,[h,h]} f. ">y>=x?i(y,x):norm(I[#0,x]  I[#0,y])"
# [2]: canvas for visualization.
600,600,1,3
# Find Knearest neighbors for each point.
# [3]: minheap
1,1,1,2
eval[0] "
const K = $1;
xy = I;
# Push distances from current point to all others in minheap.
i[#3,h(#3)1] = 0; # Fast way to clear minheap
repeat(h,k,k!=y?da_push_heap([i(#1,k,y),k]));
# Draw the Kclosest connections in canvas.
repeat (K,k,
ind = da_pop_heap();
nxy = I[ind[1]];
color = k==0?[255,255,64]:k==1?[255,128,16]:[255,0,0];
# polygon(#2,2,xy[0],xy[1],nxy[0],nxy[1],1,color);
run('line_aa[2] ',xy[0],',',xy[1],',',nxy[0],',',nxy[1],',1,',v2s(color)); # Lot slower but prettier
);
I"
eval[0] "ellipse(#2,i0,i1,5,5,0,1,255); I"
k[2] r2dx 400
In the example above, the colors for the connecting lines are : yellow
=closest, orange
=2ndclosest and red
=3rdclosest (or +).
Heap structures are in fact helpful when developing algorithms that involve graphs, such as the famous Djikstra algorithm. G’MIC already had the djikstra
command, but now we can imagine that someone could implement its own custom version of Djikstra more easily than before.
I’ve built new binary packages for 3.3.2 prereleases, including these two new commands, so feel free to test.
Cheers.
EDIT: I forgot to say that of course, you can manage maxheaps too, just insert negative values in your heap.