تحلیل سرشکن (پشته)

نحوه‌ی ساخت پشته از پایین به بالا

http://cs.stackexchange.com/questions/11415/how-to-perform-bottom-up-construction-of-heaps

در انتهای آرایه برگها هستند که پدر هیچ گره‌ی دیگری نیستند. حداکثر ارتفاع یک عدد در درخت پشته، log i است که i تعداد عناصر موجود در سمت راست آن در نمایش آرایه است.

پس در مجموع زمان O(n) است پس زمان سرشکن هر عمل O(1) است. (مشابه مثال خرس! می‌توانیم بگوییم که هر بار نصف گره‌های باقیمانده برگ هستند.)

مثال خرس: یک خرس در غار خود گوشت‌های با اندازه‌های 1,...,n دارد و هر روز یا یک گوشت فرد را کامل می‌خورد یا یک گوشت زوج را نصف می‌کند و نصف آن را می‌خورد. خرس اگر هر روز گوشت بخورد زنده می‌ماند. خرس چقدر عمر می‌کند؟

جواب: تحلیل سرشکن زمان 2 را برای هر گوشت می‌دهد. (تعداد روزهایی که خرس را زنده نگه می‌دارد.) پس خرس 2n روز زنده می‌ماند.

T(n) = n+T(n/2) = n(1+1/2+1/4+...) = 2n

(تصاعد هندسی)