The standard algorithm for hierarchical agglomerative clustering (HAC) has a time complexity of formula_1 and requires formula_2 memory, which makes it too slow for even medium data sets. However, for some special cases, optimal efficient agglomerative methods (of complexity formula_3) are known: SLINK for single-linkage and CLINK for complete-linkage clustering. With a heap, the runtime of the general case can be reduced to formula_4, an improvement on the aforementioned bound of formula_1, at the cost of further increasing the memory requirements. In many cases, the memory overheads of this approach are too large to make it practically usable.