Jeśli budujesz kopiec metodą bottom-up (heapify), to większość węzłów jest blisko liści i przesuwa się o małą liczbę poziomów. Suma pracy dla wszystkich węzłów tworzy malejącą serię, która daje O(n). Wstawianie elementów po kolei to O(n log n), ale heapify bottom-up to O(n).