ორობითი გროვა

Binary Heap

        გროვა არის მონაცემთა სტრუქტურა რომელშიც მონაცემები ისე არიან მოწესრიგებული რომ მონაცემების ექსტრემუმებზე წვდომა გვაქვს განსაკუთრებით ადვილად. არსებობს მაქსიმუმისა და მინიმუმის გროვები, მაქსიმუმის გროვაში ჩვენ მაქსიმალური მნიშვნელობის ელემენტს შეგვიძლია მინწვდეთ ერთ ოპერაციაში, ხოლო მინიმუმის გროვაში მინიმუმს. ამოცანის სპეციფიკიდან გამომდინარე უნდა გამოვიყენოთ შესაბამისი ტიპის გროვა. მაქსიმუმისა და მინიმუმის გროვის მუშაობის პრინციპი არის ერთი ამიტომ მაგალითისათვის ჩვენ განვიხილოთ მინიმუმის გროვა. ახლა რაც შეეხება თვითონ მის სტრუქტურას.

  გროვა არის ორობითი ხე, თუმცა უბრალო ორობითი ხისაგან ის განსხვავდება შემდეგი თვისებით: გროვის ნებისმიერ კვანძში შვილობილი კვანძის  მნიშვნელობა არ უნდა აღემატებოდეს მშობელი კვანძისას. ამ თვისებას გროვის ძირითად თვისებას უწოდებენ. გროვის ხე არ უნდა იყოს არათანაბრად გაზრდილი. ხე უნდა იზრდებოდეს სიმაღლეში თანაბრად. რაც გვაძლევს იმის საშუალებას რომ გროვა განვათავსოთ მასივში. ამ შემთხვევაში მეხსიერების გამოყოფა/განთავისუფლება მოხდება უფრო სწრაფად და თავიდან ავიცილებთ მეხსიერების დეფრაგმენტაციას რაც თავის მხრივ უფრო ანელებს მეხსიერებაზე წვდომას. გროვის მასივში განთავსებისას იმ  წვეროს მარცხენა შვილის ინდექსი, რომელიც მოტავსებულია მასივის i-ურ ელემენტში იქნება 2*i ხოლო მარჯვენა შვილის ინდექსი 2*i+1. ქვემოთ მოცემულ სურათზე ნაჩვენებია მაქსიმუმის ორობითი გროვა. წვეროები მოთავსებულია რგოლებში, ასევე ნაჩვენებია როგორ განლაგდება მოცემული გროვა მასივში.

  მოცემულ გროვაში ნებისმიერი წვერო შეგვიძლია დავახასიათოთ სიმაღლით, ანუ რა სიმაღლეზე იმყოფება ეს წვერო ხის ძირიდან(თავად ძირი იმყოფება ნულოვან სიმაღლეზე). რადგან მოცემულია ორობითი გროვა და რადგანაც ის სტაბილურად იზრდება სიმაღლეში, ამიტომ n ელემენტისაგან შემგარ გროვაში h სიმაღლის მქონე ელემენტების რაოდენობა არ აღემატება n/(2^(h-1))-ს, ხოლო სიმაღლე არ აღემატება log(n)-ს. მაგ: როცა n არის [2,3] დიაპაზონში ამ დროს ხის სიმაღლე არის 1(რადგან log(2) უდრის 1-ს), როცა n არის [4,7] დიაპაზონში სიმაღლე არის 2(რადგან log(4) უდრის 2-ს) და ა.შ.

განვიხილოთ გროვაზე განმარტებული ოპერაციები:

1. ელემენტის ჩამატება: ახლად შემოსული ელემენტი გროვაში ემატება ყოველთვის ბოლო ელემენტად. მაგალითად ზემოთ მოცემულ გროვაში თუ ჩავამატებთ ელემენტს მისი ნომერი იქნეაბ 11 და ის გახდება მე-5 ელემენტის მარჯვენა შვილი. გროვაში ელემენტის ჩამატებამ შესაძლოა გამოიწვიოს გროვის ძირითადი თვისების დარღვევა, ამისათვის რომ ეს არ მოხდეს უნდა შემოწმდეს თუ ახალი ელემენტის მნიშვნელობა დიდია მის მშობლის მნიშნველობაზე მაშინ მათ უნდა გავუცვალოთ ადგილები და ეს პროცედურა გავიმეოროდ მანამ სანამ ახალი ელემენტი არ იპოვნის თავის ადგილს. თუ ხის სიმაღლე არის h მაშინ ამ პროცესს შესაძლოა დაჭირდეს მაქსიმუმ h შემოწმება, ამიტომ გროვაში ახალი ელემენტის ჩამატების დროითი სირთულე არის O(log(n)).
2. ელემენტის ამოგდება: როცა გვსურს გროვიდან ელემენტის ამოგდება, ეს ელემენტი უნდა ჩავანაცვლოთ გროვის ბოლო ელემენტით. ამან შესაძლოა გამოიწვიოს ძირითადი თვისების დარღვევა. ამიტომ მის აღსადგენად მიმდინარე ელემენტის შვილებში უნდა ავარჩიოთ მაქსიმალური მნიშვნელობის მქონე, თუ მასთან მიმართებაში  ირღვევა  გროვის ძირითადი თვისება, უნდა გავუცვალოთ მათ ადგილები და ასე გავიმეოროთ მანამ, სანამ ეს ელემენტი არ მოძებნის თავის ადგილს. ამ პროცედურას ქვია Heapify. ეს შემოწმება შეიძლება მოხდეს მაქსიმუმ h-ჯერ, ამიტომ გროვიდან ელემენტის ამოგდების დროითი სირთულე არის O(log(n)).
3. მაქსიმუმზე წვდომა: გროვის ძირითადი თვისებიდან გამომდინარე მაქსიმალური მნიშვნელობის მქონე ელემენტი ზის ყოველთვის გროვის ძირში. ასე რომ მაქსიმუმზე  წვდომის დროითი სირთულე არის O(1).

ელემენტების მოცემული მიმდევრობიდან გროვის ასაგებად არსებობს რამოდენიმე მეთოდი:

1. მიმდევრობის პირველი ელემენტი ჩავამატოთ გროვის ძირად, დაწყებული მეორე ელემენტიდან მიმდევრობის ბოლომდე თითოეული ელემენტი ჩავამატოთ გროვაში, მაშინ ამ მეთოდით გროვის აგების დროითი სირთულე იქნება O(n log(n)).
2. მეორე მეთოდით ხდება ჯერ მოცემული ელემენტების ერთბაშად მოთავსება გროვაში და შემდეგ Heapify პროცედურის დახმარებით გროვის ძირითადი თვისების აღდგენა. აქვე უნდა აღვნიშნოთ რომ Heapify პროცედურის გამოძახებას აზრი აქვს მხოლოდ იმ ელემენტებისათვის რომლებსაც ჰყავთ შვილები(არ არიან ფოთლები). ფოთლების რაოდენობა კი n ელემენტიან გროვაში n/2-ს უტოლდება. ჩვენ Heapify-ს გამოძახება დაგვჭირდება დანარჩენი n/2 ელემენტისათვის. ასეთი მეთოდით გროვის აგების დროითი სირთულეა O(n).

ახლა განვიხილოთ საილუსტრაციო მაგალითი, ავაგოთ გროვა რიცხვების მოცემული მიმდევრობისათვის. ქვემოთ მოყვანილი პროგრამული კოდი დაწერილია C-ზე:

#include <stdlib.h>

void Heapify( int k, int a[], int N )
{
    int v;
    int leftChild, rightChild, maxValueChild;
    v = a[k];

    while ( k < N/2 )
    {
        leftChild = (!k)?1:2*k;
        rightChild = leftChild+1;

        //მიმდინარე ელემენტს ყავს ორივე შვილი
        if( rightChild < N )
        {
            if( a[leftChild] < a[rightChild] ) //შევადაროთ შვილების მნიშვნელობები
                maxValueChild = rightChild;
            else
                maxValueChild = leftChild;
        }else if( leftChild < N ) //ელემენტს ყავს მხოლოდ მარცხენა შვილი
            maxValueChild = leftChild;

        if( v >= a[maxValueChild] ) //შევადაროთ მშობელს, თუ არ აღემატება გავჩერდეთ
            break;

        //ავიტანოთ მაქსიმალური მნიშვნელობის მქონე შვილი მშობლის ადგილზე
        a[k] = a[maxValueChild];
        //ელემენტის მიმდინარე პოზიციად შევინახოთ მაქსიმალური მნიშვნელობის მქონე შვილის პოზიცია
        k = maxValueChild;

    }

    a[k] = v; //გადმოვიტანოთ მოძრავი ელემენტი დადგენილ პოზიციაზე
}

void BuildHeap( int* a, unsigned int N )
{
    int k;
    //გავირბინოთ ყველა ელემენტზე ფოთლების გარდა
    for( k=N/2; k>=0; --k )
        Heapify( k, a, N );
}

int main()
{
    int buffer[100];
    int i;
    for( i=0; i<100; i++ )
        buffer[i] = ( rand()/((double)RAND_MAX) )*1000;
    
    BuildHeap( buffer, 100 );
    return 0;
}

        Heapify ფუნქცია ახდენს გროვის ძირითადი თვისების აღდგენას როცა ეს თვისება დარღვეულია k-ურ ელემენტში. BuildHeap ფუნქცია აგებს გროვას ზემოთ მოყვანილი მე-2 მეთოდის მიხედვით. STL-ს აქვს ორობითი გროვის კონტეინერი stl::priority_queue, მასზე განმარტებულია შემდეგი ფუნქციები:

1. empty - გროვის გასუფთავება.
2. pop - ექსტრემუმის ამოგდება.
3. push - ელემენტის ჩამატება.
4. size - ელემენტების რაოდენობა.
5. top - ექსტრემუმის მნიშვნელობა.

        გროვებს კარგი გამოყენება აქვს ბევრ სხვადასხვა ამოცანაში და ვფიქრობ ეს პოსტი სასარგებლო უნდა იყოს მკითხველისათვის, ვეცდები შემდეგ პოსტებში განვიხილო მისი გამოყენების კონკრეტული მაგალითები.