В шестой главе учебника Кормена описывается пирамидальная сортировка, реализуемая с помощью дерева, которое, в свою очередь, реализуется с помощью массива. Причем, если узел дерева хранится в элементе массива a[i], то его левый дочерний узел хранится в элементе a[2i], а правый - в a[2i+1]. Но ведь в таком случае произойдет наложение элементов или между узлами дерева, хранимыми в массиве будет пространство свободных элементов массива, увеличивающееся в геометрической прогрессии с ростом дерева, что приведет к неэффективному использованию памяти. Или я что-то не понимаю? И вообще, для сортировки такого вида используются массивы, или применяются динамические структуры данных?

Ну да, досадная невнимательность! Не будет свободных элементов.