هرم کمینه-بیشینه

مثالی از هرم کمینه-بیشینه

در علوم رایانه، هرم کمینه-بیشینه یک صف اولویت دوطرفه (double-ended priority queue) است که نسخهٔ اصلاح شدهٔ هرم دودویی می‌باشد. هرم کمینه-بیشینه همانند هرم دودویی به صورت درخت دودویی کامل نشان داده می‌شود، اما گره‌های آن از ترتیب خاص موجود در هرم کمینه یا هرم بیشینه پیروی نمی‌کنند. مقدار هرکدام از گره‌های سطح زوج در درخت مفروض بزرگتر از نوادگانش می‌باشد، به‌طور مشابه مقدار هرکدام از گره‌های سطح فرد کوچکتر از نوادگانش می‌باشد.

مانند هرم دودویی، هرم کمینه-بیشینه اعمال درج و حذف را در (O(log n انجام می‌دهد، همچنین در (O(n نیز ساخته می‌شود و اغلب توسط یک آرایه پیاده‌سازی می‌شود. اعمال ()findMin و ()findMax در زمان‌های ثابت انجام می‌شوند.

مفاهیمویرایش

معرفیویرایش

  • هرم کمینه-بیشینه یک درخت دودویی کامل است که متناوباً دارای سطو
  • هر کدام از عناصر این داده ساختار مقداری دارد که کلید نامیده می‌شود. گره ریشه معمولاً در سطح کمینه قرار دارد. فرض کنید x هر کدام از گره‌های هرم کمینه-بیشینه باشد. اگر x در سطح کمینه (بیشینه) باشد آنوقت عنصر x در درختی به ریشه x از تمامی عناصر زیردرخت خود کوچکتر (بزرگتر) است. گره‌ای در سطح کمینه (بیشینه) با نام گره کمینه (بیشینه) خوانده می‌شود.

عملیات کمینه-بیشینهویرایش

  • درج یک عنصر با کلید دلخواه
  • حذف بزرگترین کلید
  • حذف کوچکترین کلید

درج یک عنصر با کلید دلخواهویرایش

برای درج یک عنصر در هرم کمینه-بیشینه باید اعمال زیر را انجام دهیم:

کلید را در هرم کمینه-بیشینه قرار می‌دهیم.

این کلید را با پدرش مقایسه می‌کنیم، اگر کوچکتر (بزرگتر) بود مطمئناً از کلید تمام گره‌های سطح بیشینه (کمینه) که از مکان فعلی کلید تا ریشه هرم قرار کوچکتر است. حال کافی است گره‌های سطح کمینه (بیشینه) بررسی شوند.

اگر کلید اضافه شده در جای درستی قرار گرفته باشد پروسه را متوقف می‌کنیم در غیر این صورت جای کلید و پدرش را عوض می‌کنیم.

  • مثالی از درج یک عنصر در هرم کمینه-بیشینه.

ما هرم کمینه-بیشینه زیر را داریم و می‌خواهیم عنصری با مقدار ۶ را در آن درج کنیم.

 

در ابتدا عنصر ۶ را در مکان مشخص شده با j قرار می‌دهیم. عنصر ۶ از پدرش کوچکتر است لذا از تمام عناصر سطوح بیشینه کمتر است. بابراین عنصر ۶ در مکان ریشه درخت قرار می‌گیرد و عنصر قبلی ریشه یک گام به پایین نقل مکان می‌کند.

اگر بخواهیم یک عنصر جدید با مقدار ۸۱ را در هرم مفروض قرار دهیم، مانند قبل جلو می‌رویم. در ابتدا عنصر ۸۱ را در مکان مشخص شده با j قرار می‌دهیم. از آنجا که عنصر ۸۱ از پدرش و تمام عناصر سطوح کمینه بیشتر است کافی است گره‌های سطح بیشینه بررسی شوند.

حذف کوچکترین کلیدویرایش

برای حذف کوچکترین کلید در هرم کمینه-بیشینه باید اعمال زیر را انجام دهیم.

گره درخت کوچکترین عنصر است.

  1. گره ریشه را حذف می‌کنیم و فرض می‌کنیم x گره‌ای باشد که در انتهای هرم قرار دارد.
  2. حال x را در هرم کمینه-بیشینه دوباره درج می‌کنیم.

برای دوباره درج کردن دو وضعیت به وجود می‌آید.

اگر ریشه هیچ فرزندی نداشته باشد، پس x می‌تواند در ریشه قرار گیرد.

فرض کنید ریشه حداقل یک فرزند داشته باشد. مقدار کمینه را پیدا می‌کنیم و این عنصر را m می‌نامیم. m یکی از فرزندان یا نوادگان ریشه است. حال شرایط زیر باید در نظر گرفته شود:

  1. اگر x.key <= h[m].key آنگاه x باید در مکان ریشه قرار گیرد.
  2. اگر x.key> h[m].key و m فرزند ریشه باشد چون m در سطح بیشینه است، هیچ فرزندی ندارد بنابراین عنصر [h[m باید در مکان ریشه و عنصر x در گره m قرار گیرد.
  3. اگر x.key> h[m].key و m از نوادگان فرزند ریشه باشد آنگاه باید عنصر [h[m در مکان ریشه قرار گیرد. حال فرض کنیم p پدر m باشد، اگر x.key> h[p].key آنگاه جایگاه [h[p و x باید عوض شود.

کد زیر حذف عنصر با کوچکترین کلید را پیاده‌سازی می‌کند.

element del_min(element heap[], int *s) { // *s: capacity of the heap
    int i, last, m, parent;
    element temp, x;

    if ((*s) == 0) {
        heap[0].key = INT_MAX;
    
        return(heap[0]);
    }

    heap[0] = heap[1];
    x = heap[(*s)--];

    /* find place to insert x */
    for (i = 1, last = (*s) / 2; i <= last;  ) {
        m = min_child_grandchild(i, *s);
    
        if (x.key <= heap[m].key) // case 1
            break;
    
        heap[i] = heap[m]; // case 2 or 3
    
        if (m <= (2 * i) + 1) { // case 2
            i = m;
        
            break;
        }
    
        /* case 3 */
        parent = m / 2;
    
        if (x.key > heap[parent].key)
            SWAP(heap[parent], x, temp);
    
        i = m;
    }

    heap[i] = x;

    return heap[0];
}

منابعویرایش

Loyola University Chicago , MIN-MAX HEAP AND DEAP DATA STRUCTURE A Research Report on MIN MAX HEAP AND DEAP DATA STRUCUTRE, February, 2014, MIN MAX HEAP AND DEAP DATA STRUCUTRE