Если предстааить себе, что ранний лисп использовал в качестве пула объектов именно кучу как дерево с предикатом сравнения, то предлагаю попробовать представить себе, что ж там за предикат сравнения такой. Он должен уметь сравнивать два произвольных лисп-значения. У меня не получается представить.
Я тут вспомнил эту тему всвязи с попытками создать контейнер с более быстрым произвольным доступом по индексу, чем у односвязного списка. Мне подумалось, что двоичная куча, иногда реализовывается в виде вектора, а что если сделать наоборот, и реализовать вектор в виде кучи. Т.е. у нас не будет свойства, что в корне лежит минимум, но будет доступ по индексу за двоичный логарифм. Может оно так и работало тогда?