هل تنطبق خاصية الكومة في تعريف الكومة الثنائية بشكل متكرر؟

Question

تعريف binary heaps تقول إنها يجب أن تكون شجرة ثنائية كاملة ويجب أن تتبع خاصية الكومة حيث وفقًا لخاصية الكومة، يكون المفتاح المخزن في كل عقدة إما أكبر من أو يساوي أو أقل من أو يساوي المفاتيح الموجودة في أبناء العقدة.

في الشجرة أعلاه، العقدة ذات القيمة 70 أكبر من العقدة الأصلية 10 التي تكسر خاصية الكومة.ومع ذلك، 70 أكبر أيضًا من 40 ويقع في الشجرة الفرعية للرقم 40.هل يمكننا القول أن خاصية الكومة تنكسر أيضًا عند 40، على الرغم من أن 40 أكبر من طفليها 10 و2؟

بعبارات بسيطة، هل يجب أن تكون كل عقدة في الشجرة الفرعية للجذر أصغر من الجذر؟

Answer 1

أعتقد أن معظم الناس سيقولون فقط أن خاصية الكومة تنطبق فقط على الرأس وأبنائه المباشرين، لأنه تعريف كافٍ للحفاظ على خاصية الكومة "العودية" في كل مكان.إنها طريقة أنظف للتفكير في الأمر (ما عليك سوى التحقق من كائنات O(1) لكل قمة للتحقق من أن الشجرة عبارة عن كومة، بدلاً من O(n) لكل قمة).

لا أعلم إذا كان هناك إجماع على هذا الأمر، وربما يفكر البعض الآخر بطريقة مختلفة.