Mound - онлайн пъзели

Mound (известен също като heap или heap) - структура на базата на дърво, в която стойностите на потомците на възела са в постоянна връзка със стойността на родителя (например стойността на родителя е не по-малка от стойността на неговия потомък).

Пълна могила

Ако могилата трябва да бъде пълна могила, трябва да бъдат изпълнени следните условия:

дървото е почти пълно, т.е. листата се появяват на последното и евентуално до последното ниво в дървото (само когато последното ниво не е напълно запълнено),

листата на последното ниво са последователно подредени отляво надясно.

Свойства на могили

Ако възприетата връзка между дъщерната стойност и родителската стойност е малцинствената връзка, тогава възелът с най-голям ключ ще бъде в горната част.

В случай на пълна двоична могила е лесно да се приложи могилата в масив съгласно следната диаграма (подобни техники съществуват и за други могили).

Чрез номериране на последващи елементи от върха на могилата от 1, а след това отляво надясно, на всяко следващо ниво на могилата можем лесно да имаме достъп до левия или десния потомък или баща, с:

Ако детето има номер

        п

        ,

    {\ displaystyle n,}

   този баща има

        п

          /

        2

    {\ displaystyle n / 2}

   (например за 7, бащата има номер 3). Използваме общата операция на разделяне.

Ако бащата има номер

        п

        ,

    {\ displaystyle n,}

   тогава лявото дете има номер

        2

        п

        ,

    {\ displaystyle 2n,}

   и правилно

        2

        п

        +

        1.