ما هو الحد الأدنى والحد الأقصى للأعداد من العناصر في كومة الارتفاع H؟

Question

جئت عبر السؤال:

ما هي الحد الأدنى والحد الأقصى للأعداد من العناصر في كومة من الارتفاع $ h $ ؟

التي توصلت إليها مع هذه النظرية: $$ \ sum_ {i= 0} ^ {h-1} 2 ^ i= 2 ^ h-1 $$

$ 2 ^ H-1 $ هي العقد الداخلية ومن المفهوم وفقا للحقيقة المفهومة. ولكن نظرا لأن أي مكان ما عدا CLRS يذكر أكواد أن تكون <قوية> شجرة ثنائية كاملة تقريبا في كل مكان يتم ذكرها كشجرة ثنائية كاملة.

الحد الأقصى لعدد العناصر يمكن حسابها بسهولة: $$ \ sum_ {i= 0} ^ {h} 2 ^ i= 2 ^ {h + 1} -1 $

لكن لا يمكنني الحصول على نقطة الحوسبة الحد الأدنى لعدد العناصر: هل يجب أن تكون: $$ 2 ^ {h} +1 $ ل $ 0 $ أو $ 2 $ خاصية الأطفال

أو يجب أن يكون: $$ 2 ^ {h} $$ for $ 0 $ أو $ 1 $ خاصية الأطفال

المرجع 1: re="nofollow noreferrer"> https://walkccc.github.io/clrs/ Chap06 / 6.1 / # 61-1

المرجع 2: heapsort

شكرا لك.

Answer 1

كومة من الارتفاع $ H $ كاملة حتى المستوى عند العمق $ H-1 $ ويحتاج إلى وجود عقدة واحدة على الأقل على المستوى $ H $ .

لذلك يجب أن يكون الحد الأدنى لعدد العقد الإجمالي على الأقل $ \ sum_ {i= 0} ^ {h-1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ h. $ ، وهذا ضيق منذ كومة مع $ 2 ^ h $ العقد لديها ارتفاع $ h $ .