En lugar de un montículo, puede utilizarse un árbol binario de búsqueda auto-balanceable, en cuyo caso la inserción y borrado siguen teniendo un coste de formula_3, mientras que la construcción de árboles a partir de secuencias de elementos ya existentes pasaría a tener un coste de formula_6.