Mound - puzzle-uri online

Mound (cunoscută și sub denumirea de heap sau heap) - o structură de date bazată pe arbori în care valorile descendenților nodului sunt în relație constantă cu valoarea părintelui (de exemplu, valoarea părintelui nu este mai mică decât valoarea descendentului său).

Movilă completă

Dacă movila trebuie să fie o movilă completă, atunci trebuie îndeplinite următoarele condiții:

copacul este aproape plin, adică frunzele apar pe ultimul nivel și, eventual, lângă ultimul nivel din copac (numai atunci când ultimul nivel nu este complet umplut),

frunzele de la ultimul nivel sunt aranjate constant de la stânga la dreapta.

Proprietățile movilelor

Dacă relația adoptată între valoarea copilului și valoarea părinte este relația minoritară, atunci nodul cu cea mai mare cheie va fi în partea de sus.

În cazul unei movile binare complete, este ușor să implementați movila într-un tablou în conformitate cu diagrama următoare (există tehnici similare pentru alte movile).

Numerotând elementele ulterioare din vârful movilei de la 1, apoi de la stânga la dreapta, la fiecare nivel ulterior al movilei putem accesa cu ușurință descendentul sau tatăl din stânga sau dreapta, cu:

Dacă copilul are un număr

        n

        .

    {\ displaystyle n,}

   acest tată are

        n

          /

        2

    {\ displaystyle n / 2}

   (de exemplu, pentru 7, tatăl are numărul 3). Folosim operația de divizare totală.

Dacă tatăl are un număr

        n

        .

    {\ displaystyle n,}

   atunci copilul stâng are un număr

        2

        n

        .

    {\ displaystyle 2n,}

   și drept

        2

        n

        +

        1.