I believe the Re-Pair algorithm used for doing linear time byte-pair encoding makes use of a similar idea: https://en.m.wikipedia.org/wiki/Re-Pair

There, instead of dates, the “priority index” reflects the frequencies of pairs seen in the input string. This leads to guaranteed O(1) runtime amortized over the input string, since the largest frequency count is bounded by the size of the input and can only decrease as merges happen.