Это не изменится. Куча - это полное двоичное дерево, которое учитывает свойство кучи. Массив - это просто удобный и простой способ его реализации.
Heapsort в зависимости от n extract-min (при условии минимальной кучи), где для каждого общего значения требуется O (log n) time.
Временная сложность этой операции одинакова при использовании традиционных реализаций массива или древовидной структуры данных.