# گِردالی‌ها به صف ...

By [Farzad Shami](https://paragraph.com/@0xshami) · 2022-08-16

---

به نام او
=========

خب موضوع این هفته‌ی ما مربوطه به یسری گردالی (یکسری شی گِرد گِرد که توش عدد مینویسن و بهم وصلشون میکنن بعد ما رو بدبخت میکنن (به اختصار گراف)).

خب حالا هر کی وارد این حوزه شده لاقل یبار با گراف سر و کله زده شده حتی به صورت تئوری توی دبیرستان. یکم یادآوریش خوبه - گراف اویلری و همیلتونی و ? ? ? ? ? ....

خب اما ما امروز قراره با همین گردالیا یه کار خفن توی node.js انجام بدیم، از طرفی میخوایم کاری رو انجام بدیم که توی پروژه‌هامون شاید خیلی باهاش سر و کله زدیم.

خب قراره چیکار کنیم ؟

قراره یه جایی رو مدیریت کنیم که تعداد زیادی آدم بهش سر میزنن و خیلی برای ما مهمه که یجوری اینارو توی صف بچنیم که

*   حق کسی ضایع نشه
    
*   همه به مراد دلشون برسن
    
*   کسی ناراضی نباشه
    
*   و از همه مهم تر خیلی سریع این چینش انجام بشه
    

خب پس کلیت کاری که ما قراره انجام بدیم اینکه یه صف درست کنیم که توش اولویت‌ها لحاظ شدن ...

نمونه ها :

*   وام دادن : شخص xایی که وارد بانک میشه برای گرفتن وام، چون پارتیش کلفت‌تره? باید بیاد اول صف .
    
*   بیمارستان : شخص Yایی وارد بیمارستان میشه و تیر خورده ? و اگه بهش رسیدگی نشه تا ده دقیقه دیگه میمیره و نفر اول صف یه جراحت ساده داره پس باید اولویت ها دوباره درست بشن .
    

خب حالا بریم ببینیم با این گردالی‌ها چطوری میتونیم اینکارو بکنیم.

باید یه درخت (دودویی) درست کنیم ! درخت چیست ؟ درخت دودویی اینجوریه که هر نفری (گره) میتونه دو تا فرزند داشته باشه یکی گره فرزند ناخلف (دست چپ پدر) و یکی بچه خوبه بابا (دست راست بابا) و اینا همشون به جد خودشون وصلن . [مطالعه بیشتر](https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%AF%D9%88%D8%AF%D9%88%DB%8C%DB%8C)

شجره نامه

خب حالا بیاید به این فکر کنیم اگه این درخت دودویی ما همینجوری تا آخر بره ممکنه یجا از یه سمتی نسل منقرض بشه و از یه سمتی ما خیلی بچه داشته باشیم خب تا اینجاش که عادیه و به نظر مشکلی نداره، اما یادتون هست که گفتم باید سرعت چینش مجدد صف باید بالا باشه، اگه ارتفاع درخت ما زیاد بشه این اصلا به نفع ما نیست. حالا راهکار چیه ؟

راهکار اینه که ما تلاش کنیم که درختمون کامل بشه. یعنی حداکثر یک گره فقط فرزند چپ داشته باشه و بقیه گره‌های دو فرزند داشته باشن به شرطی که جزو ردیف آخر نباشن. با این راهکار ارتفاع درخت ما با n عنصر برابر میشه با ⌊log n⌋ .

خب تا اینجا با کلیت کاری که میخوایم کنیم آشنا شدیم

حالا میخوایم طی یک حرکت طوفانی این گردالیا رو شماره گذاری کنیم و وارد بخش اصلی قضیه بشیم.

الان توی این شکل 50 ریشه ماست و فرزند های اون 17 و 72 هستن و الی آخر ...

اگه ما بیایم و همه‌ی این عناصر رو توی یه آرایه بریزیم آرایه ما یه همچنین شکلی میگیره ...

یعنی هر والد دو تا فرزند تو خونه‌های (2 \* شماره خونه خودش) و (2 \* شماره خونه خودش + 1) داره .

بعد از فهمیدن این وارد حالا باید ببینیم الگوریتم ما چه مدلی کار میکنه، الگوریتم ما میگه

*   ریشه بزرگترین عنصر در این درخته .
    
*   هر والد از فرزندهاش بزرگتره . هِمین ... ?
    

خب شروع میکنیم اول از همه پوشه گردالی‌های مهربون رو میسازیم، و یه فایل به اسم maxHeap.js میسازیم توش

    // maxHeap.js
    
    class MaxHeap {
        constructor() {
        this.heapContainer = [];
        }
    }
    
    module.exports = MaxHeap;
    

توابع اینکه آیا بچه راست داره یا نداره و والدش کیه و اینارو اضافه میکنیم، اگه کدا رو نگاه کنید زیاد مفهوم خاصی توشون نیست و به سادگی متوجه میشد، یسری تابع هستن که بررسی هایی رو انجام میدن و و تو قسمت های اصلی به دردمون میخورن .

    MaxHeap.prototype.getLeftChildIndex = function(parentIndex) {
        return 2 * parentIndex + 1;
    };
    MaxHeap.prototype.getRightChildIndex = function(parentIndex) {
        return 2 * parentIndex + 2;
    };
    MaxHeap.prototype.getParentIndex = function(childIndex) {
        return Math.floor((childIndex - 1) / 2);
    };
    MaxHeap.prototype.hasParent = function(childIndex) {
        return this.getParentIndex(childIndex) >= 0;
    };
    MaxHeap.prototype.hasLeftChild = function(parentIndex) {
        return this.getLeftChildIndex(parentIndex) < this.heapContainer.length;
    };
    MaxHeap.prototype.hasRightChild = function(parentIndex) {
        return this.getRightChildIndex(parentIndex) < this.heapContainer.length;
    };
    MaxHeap.prototype.leftChild = function(parentIndex) {
        return this.heapContainer[this.getLeftChildIndex(parentIndex)];
    };
    MaxHeap.prototype.rightChild = function(parentIndex) {
        return this.heapContainer[this.getRightChildIndex(parentIndex)];
    };
    MaxHeap.prototype.parent = function(childIndex) {
        return this.heapContainer[this.getParentIndex(childIndex)];
    };
    

خب حالا میرسیم به توابع درست درمون :

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

یه تابع برای تعویض دو عنصر مینویسم:

    MaxHeap.prototype.swap = function(indexOne, indexTwo) {
        const tmp = this.heapContainer[indexTwo];
        this.heapContainer[indexTwo] = this.heapContainer[indexOne];
        this.heapContainer[indexOne] = tmp;
    };
    

یه تابع هم مینوسیم که ریشه رو به ما برگردونه :

    MaxHeap.prototype.peek = function() {
        if (this.heapContainer.length === 0) {
            return null;
        }
        return this.heapContainer[0];
    };
    

این دو تابع هم مفهوم خاصی توشون نبود، خب به این جریان فک کنید که مریض تیر خورده ما وارد بیمارستان میشه پس باید اولویت ها بر حسب الگوریتمی ک گفتم دوباره درست بشه پس تابع add رو به این شکل مینوسیم.

    MaxHeap.prototype.add = function(item) {
        this.heapContainer.push(item);
        this.heapifyUp();
        return this;
    };
    

تابع heapifyUp وظیفه مرتب سازی رو داره (با والد بررسی میکنه اگه بزرگتر از والد بود با والد جابجا میشه

     MaxHeap.prototype.heapifyUp = function(customStartIndex) {
         let currentIndex = customStartIndex || this.heapContainer.length - 1;
         while ( this.hasParent(currentIndex) && 
         !this.pairIsInCorrectOrder ( this.parent( currentIndex), this.heapContainer[currentIndex] )) {
             this.swap(currentIndex, this.getParentIndex(currentIndex));
             currentIndex = this.getParentIndex(currentIndex);
             }
     };
    

اگه به کد بالا توجه کنید یه تابع به اسم pairIsInCorrectOrder میبینید حالا ما این تابع رو مینویسیم و یسری تغییرات جزیی ایجاد میکنیم که دلیلشو بعد نوشتن توابع و تغییرات میگم

اول میایم و یه فایل جدید با اسم Comparetor.js ایجاد میکنیم.

    // Comparator.js
    
    class Comparator {
        constructor(compareFunction) {
        this.compare = compareFunction || this.defaultCompareFunction;
        }
    }
    Comparator.prototype.defaultCompareFunction = function(a, b) {
        if (a === b) {
            return 0;
        }
        return a < b ? -1 : 1;
    };
    Comparator.prototype.equal = function(a, b) {
        return this.compare(a, b) === 0;
    };
    Comparator.prototype.greaterThan = function(a, b) {
        return this.compare(a, b) > 0;
    };
    Comparator.prototype.greaterThanOrEqual = function(a, b) {
         return this.greaterThan(a, b) || this.equal(a, b);
    };
    
    module.exports = Comparator;
    

همونطور که از اسمش مشخصه برای بررسی کردن دوتا عنصر ما این کلاسو نوشتیم

حالا وارد کلاس اصلیمون میشیم و کد سازنده رو بدین گونه باز نویسی میکنیم و تابع pairIsInCorrectOrder رو هم اضافه میکنیم.

    const Comparator = require("./Comparetor");
    class MaxHeap {
        constructor(comparatorFunction) {
        this.heapContainer = [];
        this.compare = new Comparator(comparatorFunction);
        }
    }
    

و در نهایت

    MaxHeap.prototype.pairIsInCorrectOrder = function(firstElement, secondElement) {
        return this.compare.greaterThanOrEqual(firstElement, secondElement);
    };
    

شاید براتون جالب باشه که چرا اینهمه لقمه رو دهنمون چرخوندیم، بحث اینه آخر این مقاله قراره یه تمرین داشته باشیم که فقط با تغییر همین دوسه بخش میشه پیاده سازیش کرد

خب حالا این شخص تیر خورده ما مورد ویزیت قرار گرفت حالا ما باید دوباره از اول صف رو بچینیم که ببینیم چند چندیم. در نتیجه یه تابع نیازه که بالاترین اولویت که رفت اولویت بعدی رو مشخص کنه و درخت ما رو باتوجه به خواسته هامون دوباره بچینه حالا باید بیایم اول از همه حذف کنیم

    MaxHeap.prototype.poll = function() {
        if (this.heapContainer.length === 0) {
            return null;
        }
        if (this.heapContainer.length === 1) {
            return this.heapContainer.pop();
        }
        const item = this.heapContainer[0];
        this.heapContainer[0] = this.heapContainer.pop();
        this.heapifyDown();
        return item;
    };
    

حالا تابع heapifyDown مینویسیم.

    MaxHeap.prototype.heapifyDown = function(customStartIndex = 0) {
        let currentIndex = customStartIndex;
        let nextIndex = null;
        
        while (this.hasLeftChild(currentIndex)) {
             if (this.hasRightChild(currentIndex) &&
                 this.pairIsInCorrectOrder(this.rightChild(currentIndex), this.leftChild(currentIndex))) {
                     nextIndex = this.getRightChildIndex(currentIndex);
             } else {
                    nextIndex = this.getLeftChildIndex(currentIndex);
             }
             if (this.pairIsInCorrectOrder(
                 this.heapContainer[currentIndex], this.heapContainer[nextIndex] )) {
                     break;
              }
              this.swap(currentIndex, nextIndex);
              currentIndex = nextIndex;
        }
    };
    

خب تموم شد . ?

### مشق شب : کدارو یجوری تغییر بدین که صف بر اساس کمترین اولویت چیده بشه .

پ.نوشت :

*   تو این مقاله من از لفظ درخت خیلی استفاده کردم که شاید اساتید بهم خرده بگیرن و در اصل ما به این ساختار میگیم هرم ( هرم = یک درخت دودویی تقریبا کامل)
    
*   من اینو با نود نوشتم ولی شما میتونید سمت فرانت هم یسری از این قبیل کارها بکنید به نظر خودم اینجوری بار روی سرور کمتره.... به زودی تجربه خودم رو خواهم گفت.
    

پیشنهادات و نظرات خودتون رو حتما برام راجع به این آموزش بنویسید و بگید دوستدارید توی سری بعدی چه چیزی راجع به دنیای این گردالی ها یاد بگیرید !

---

*Originally published on [Farzad Shami](https://paragraph.com/@0xshami/UZy5C40Kf9ucOy0xQnru)*