ما هو الحد الأدنى والحد الأقصى للأعداد من العناصر في كومة الارتفاع H؟
-
29-09-2020 - |
سؤال
جئت عبر السؤال:
ما هي الحد الأدنى والحد الأقصى للأعداد من العناصر في كومة من الارتفاع $ 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
شكرا لك.
المحلول
كومة من الارتفاع $ H $ كاملة حتى المستوى عند العمق $ H-1 $ ويحتاج إلى وجود عقدة واحدة على الأقل على المستوى $ H $ .
لذلك يجب أن يكون الحد الأدنى لعدد العقد الإجمالي على الأقل $ \ sum_ {i= 0} ^ {h-1} 2 ^ i + 1= 2 ^ {h} -1 + 1= 2 ^ h. $ ، وهذا ضيق منذ كومة مع $ 2 ^ h $ العقد لديها ارتفاع $ h $ .