مرتب سازی هیپ (Heap Sort) در جاوا — راهنمای جامع

در این راهنما با طرز کار مرتب‌سازی و روش پیاده‌سازی آن در جاوا آشنا می‌شویم. مرتب‌سازی هیپ یا Heap Sort چنان که از نامش برمی‌آید بر مبنای ساختمان داده هیپ اجرا می‌شود. برای درک صحیح هیپ ابتدا باید با ساختمان آن و روش پیاده‌سازی‌اش آشنا شویم.

ساختمان داده هیپ

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

1. مقدار هر گره باید کمتر یا مساوی مقادیر ذخیره شده در فرزندان آن باشد.
2. هیپ یک درخت کامل است یعنی کمترین ارتفاع ممکن را دارد.

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

فیلم آموزش ساختمان داده ها و الگوریتم ها در جاوا Java در فرادرس

کلیک کنید

انواع هیپ

هیپ گونه‌های بسیار مختلفی دارد که تنها تفاوت آن‌ها از نظر برخی جزییات پیاده‌سازی با هم متفاوت هستند. برای نمونه آن چه در بخش فوق توصیف کردیم، یک Min-Heap یا هرم کمینه است، زیرا مقدار والد همواره کمتر از فرزندانش است. به طور جایگزین می‌توان Max-Heap یا هرم بیشینه نیز داشت که در آن والد همواره بزرگ‌تر از فرزندانش است. از این رو بزرگ‌ترین عنصر در گره ریشه قرار خواهد داشت.

ما می‌توانیم از میان پیاده‌سازی‌های مختلف درخت یکی را برای هیپ انتخاب کنیم. سرراست‌ترین گزینه درخت دودویی است. در درخت دودویی هر گره می‌تواند حداکثر دو فرزند داشته باشد. ما آن‌ها را برگ چپ و برگ راست می‌نامیم. ساده‌ترین روش برای الزام به قاعده دوم بخش فوق استفاده از درخت دودویی کامل است. یک درخت دودویی کامل داری قواعد ساده‌ای به شرح زیر است:

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

در مثال‌های زیر نمونه‌هایی از قواعد فوق را می‌بینید:

1        2      3        4        5        6         7         8        9       10
()       ()     ()       ()       ()       ()        ()        ()       ()       ()
        /         \     /  \     /  \     /  \      /  \      /        /        /  \
       ()         ()   ()  ()   ()  ()   ()  ()    ()  ()    ()       ()       ()  ()
                               /          \       /  \      /  \     /        /  \
                              ()          ()     ()  ()    ()  ()   ()       ()  ()
                                                                            /
                                                                           ()

درخت‌های 1، 2، 4، 5 و 7 از قواعد فوق پیروی می‌کنند. درخت‌های 3 و 6 از قاعده 1 تخطی کرده‌اند. درخت‌های 8 و 9 از قاعده دوم تخطی کرده‌اند و درخت شماره 10 قاعده سوم را نقض می‌کند.

ما در این راهنما روی Min-Heap با پیاده‌سازی درخت دودویی متمرکز می‌شویم.

درج عناصر

ما باید همه عملیات را به ترتیبی پیاده‌سازی کنیم که هیپ بدون تغییر بماند. بدین ترتیب می‌توانیم هیپ را با استفاده از درج‌های مکرر بسازیم. بنابراین در ادامه روی یک عمل درج منفرد متمرکز می‌شویم:

1. یک برگ جدید بسازید که سمت راست‌ترین جایگاه ممکن روی عمیق‌ترین سطح است و آیتم را در این گره ذخیره کنید.
2. اگر این عنصر کمتر از والدینش باشد، جای آن‌ها را با هم عوض می‌کنیم.
3. گام 2 را تا زمانی که عنصر کمتر از والدینش باشد و یا به ریشه جدید تبدیل شود ادامه می‌دهیم.

توجه کنید که گام 2 فوق، قاعده هیپ را نقض نمی‌کند، زیرا اگر مقدار یک گره را با مقدار کمتر عوض کنیم همچنان کمتر از فرزندانش خواهد بود.

در ادامه یک مثال عملی را بررسی می‌کنیم. فرض کنید می‌خواهیم مقدار 4 را در این هیپ درج کنیم:

     2
    / \
   /   \
  3     6
 / \
5   7

نخستین گام این است که یک برگ جدید ایجاد می‌کنیم تا مقدار 4 را در آن وارد نماییم:

1     2
2    / \
3   /   \
4  3     6
5 / \   /
65   7 4

از آنجا که 4 کمتر از والد خود، 6 است، جای آن‌ها را با هم عوض می‌کنیم:

     2
    / \
   /   \
  3     4
 / \   /
5   7 6

اکنون بررسی می‌کنیم که آیا 4 کمتر از والد خود است یا نه. از آنجا که والد آن 2 است، در این مرحله متوقف می‌شویم. هیپ همچنان معتبر است و ما مقدار 4 را درج کرده‌ایم.

اکنون تصور کنید می‌خواهیم مقدار 1 را در این هیپ درج کنیم:

     2
    / \
   /   \
  3     4
 / \   / \
5   7 6   1

ما باید جای 1 و 4 را تعویض کنیم:

     2
    / \
   /   \
  3     1
 / \   / \
5   7 6   4

اکنون باید جای 1 و 2 را عوض کنیم:

1     1
2    / \
3   /   \
4  3     2
5 / \   / \
65   7 6   4

از آنجا که 1 به ریشه جدید تبدیل شده است در این مرحله متوقف می‌شویم.

پیاده‌سازی هیپ در جاوا

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

     0
    / \
   /   \
  1     2
 / \   /
3   4 5

تنها کاری که باید انجام دهیم، این است که دقت کنیم چه تعداد عنصر باید در درخت ذخیره کنیم. بدین ترتیب اندیس عنصر بعدی که می‌خواهیم درج کنیم، اندازه آرایه خواهد بود.

فیلم آموزش برنامه نویسی جاوا Java در فرادرس

کلیک کنید

با این روش اندیس‌گذاری می‌توانیم اندیس گره‌های والد و فرزند را محاسبه کنیم:

• والد:  2/  (index – 1)
• فرزند چپ: 2index +2
• فرزند راست:  2index + 2

از آنجا که نمی‌خواهیم دردسر تخصیص مجدد آرایه را داشته باشیم، آن پیاده‌سازی را با بهره‌گیری از ArrayList از آن چه که هست بازهم ساده‌تر می‌کنیم.

پیاده‌سازی یک درخت دودویی کامل چیزی مانند زیر است:

1class BinaryTree<E> {
2 
3    List<E> elements = new ArrayList<>();
4 
5    void add(E e) {
6        elements.add(e);
7    }
8 
9    boolean isEmpty() {
10        return elements.isEmpty();
11    }
12 
13    E elementAt(int index) {
14        return elements.get(index);
15    }
16 
17    int parentIndex(int index) {
18        return (index - 1) / 2;
19    }
20 
21    int leftChildIndex(int index) {
22        return 2 * index + 1;
23    }
24 
25    int rightChildIndex(int index) {
26        return 2 * index + 2;
27    }
28 
29}

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

1class Heap<E extends Comparable<E>> {
2 
3    // ...
4 
5    void add(E e) {
6        elements.add(e);
7        int elementIndex = elements.size() - 1;
8        while (!isRoot(elementIndex) && !isCorrectChild(elementIndex)) {
9            int parentIndex = parentIndex(elementIndex);
10            swap(elementIndex, parentIndex);
11            elementIndex = parentIndex;
12        }
13    }
14 
15    boolean isRoot(int index) {
16        return index == 0;
17    }
18 
19    boolean isCorrectChild(int index) {
20        return isCorrect(parentIndex(index), index);
21    }
22 
23    boolean isCorrect(int parentIndex, int childIndex) {
24        if (!isValidIndex(parentIndex) || !isValidIndex(childIndex)) {
25            return true;
26        }
27 
28        return elementAt(parentIndex).compareTo(elementAt(childIndex)) < 0;
29    }
30 
31    boolean isValidIndex(int index) {
32        return index < elements.size();
33    }
34 
35    void swap(int index1, int index2) {
36        E element1 = elementAt(index1);
37        E element2 = elementAt(index2);
38        elements.set(index1, element2);
39        elements.set(index2, element1);
40    }
41     
42    // ...
43 
44}

دقت داشته باشید که چون نیاز داریم عناصر را مقایسه کنیم، باید آن‌ها را با استفاده از java.util.Comparable پیاده‌سازی کنیم.

مرتب‌سازی هیپ

از آنجا که ریشه هیپ همواره شامل کوچک‌ترین عنصر است، ایده اصلی مرتب‌سازی هیپ کاملاً ساده است: گره‌های ریشه را تا زمانی که هیپ کاملاً خالی شود، حذف می‌کنیم. تنها کاری که باید انجام دهیم یک عملیات حذف است که هیپ را در حالت سازگار حفظ می‌کند. ما باید مطمئن شویم که ساختار درخت دودویی یا مشخصه هیپ نقض نمی‌شود.

فیلم آموزش ساختمان داده ها و الگوریتم ها در جاوا Java در فرادرس

کلیک کنید

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

این کار تعویض را تا زمانی که عنصر به یک برگ تبدیل شود و یا کمتر از همه فرزندانش باشد، ادامه می‌دهیم. برای مثال، در هیپ زیر می‌خواهیم ریشه را از درخت حذف کنیم:

     1
    / \
   /   \
  3     2
 / \   / \
5   7 6   4

ابتدا برگ آخر را در ریشه قرار می‌دهیم:

     4
    / \
   /   \
  3     2
 / \   /
5   7 6

سپس از آنجا که بزرگ‌تر از هر دو فرزند خود است، آن را با کمترین فرزندش یعنی 2 عوض می‌کنیم:

     2
    / \
   /   \
  3     4
 / \   /
5   7 6

4 کمتر از 6 است و بنابراین در این مرحله متوقف می‌شویم.

پیاده‌سازی مرتب‌سازی هیپ در جاوا

بر اساس همه آن چه تا به اینجا گفتیم، حذف کردن ریشه (popping) کاری مانند زیر است:

1class Heap<E extends Comparable<E>> {
2 
3    // ...
4 
5    E pop() {
6        if (isEmpty()) {
7            throw new IllegalStateException("You cannot pop from an empty heap");
8        }
9 
10        E result = elementAt(0);
11 
12        int lasElementIndex = elements.size() - 1;
13        swap(0, lasElementIndex);
14        elements.remove(lasElementIndex);
15 
16        int elementIndex = 0;
17        while (!isLeaf(elementIndex) && !isCorrectParent(elementIndex)) {
18            int smallerChildIndex = smallerChildIndex(elementIndex);
19            swap(elementIndex, smallerChildIndex);
20            elementIndex = smallerChildIndex;
21        }
22 
23        return result;
24    }
25     
26    boolean isLeaf(int index) {
27        return !isValidIndex(leftChildIndex(index));
28    }
29 
30    boolean isCorrectParent(int index) {
31        return isCorrect(index, leftChildIndex(index)) && isCorrect(index, rightChildIndex(index));
32    }
33     
34    int smallerChildIndex(int index) {
35        int leftChildIndex = leftChildIndex(index);
36        int rightChildIndex = rightChildIndex(index);
37         
38        if (!isValidIndex(rightChildIndex)) {
39            return leftChildIndex;
40        }
41 
42        if (elementAt(leftChildIndex).compareTo(elementAt(rightChildIndex)) < 0) {
43            return leftChildIndex;
44        }
45 
46        return rightChildIndex;
47    }
48     
49    // ...
50 
51}

چنان که پیش‌تر گفتیم، مرتب‌سازی صرفاً به ایجاد هیپ و حذف کردن مکرر ریشه مربوط است:

1class Heap<E extends Comparable<E>> {
2 
3    // ...
4 
5    static <E extends Comparable<E>> List<E> sort(Iterable<E> elements) {
6        Heap<E> heap = of(elements);
7 
8        List<E> result = new ArrayList<>();
9 
10        while (!heap.isEmpty()) {
11            result.add(heap.pop());
12        }
13 
14        return result;
15    }
16     
17    static <E extends Comparable<E>> Heap<E> of(Iterable<E> elements) {
18        Heap<E> result = new Heap<>();
19        for (E element : elements) {
20            result.add(element);
21        }
22        return result;
23    }
24     
25    // ...
26 
27}

کارکرد این الگوریتم را با تست زیر می‌توانیم بررسی کنیم:

1@Test
2void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList() {
3    // given
4    List<Integer> elements = Arrays.asList(3, 5, 1, 4, 2);
5     
6    // when
7    List<Integer> sortedElements = Heap.sort(elements);
8     
9    // then
10    assertThat(sortedElements).isEqualTo(Arrays.asList(1, 2, 3, 4, 5));
11}

توجه کنید که امکان ارائه یک پیاده‌سازی که مرتب‌سازی درجا انجام دهد نیز وجود دارد. این کار بدان معنی است که نتیجه را در همان آرایه‌ای که عناصر را در خود دارد ارائه کنیم. به علاوه در این روش به هیچ تخصیص حافظه آنی نیاز نداریم. با این حال، درک آن پیاده‌سازی کمی دشوارتر خواهد بود.

پیچیدگی زمانی

مرتب‌سازی هیپ دو مرحله کلیدی دارد که یک درج کردن عنصر و دیگری حذف گره ریشه است. هر دو مرحله دارای پیچیدگی زمانی (O(log n هستند. از آنجا که هر دو مرحله n بار تکرار می‌شوند، پیچیدگی مرتب‌سازی کلی برابر با (O(n log n خواهد بود.

دقت کنید که ما به هزینه تخصیص مجدد آرایه اشاره نکردیم، اما از آنجا که پیچیدگی آن (O(n است تأثیری روی پیچیدگی کلی نخواهد داشت. ضمناً چنان که پیش‌تر گفتیم، امکان پیاده‌سازی مرتب‌سازی به صورت درجا نیز وجود دارد. بدین ترتیب نیازی به تخصیص مجدد آرایه هم وجود نخواهد داشت. همچنین باید اشاره کنیم که در هیپ 50% از عناصر برگ هستند و 75% از آن‌ها عناصری هستند که در پایین‌ترین سطح قرار دارند. از این رو اغلب عملیات درج، به چیزی بیش از دو گام نیاز نخواهند داشت.

توجه داشته باشید که در داده‌های دنیای واقعی، الگوریتم Quicksort کارآمدتر از مرتب‌سازی هیپ است. نکته اینجا است که الگوریتم مرتب‌سازی هیپ همواره سناریوی بدترین حالت یعنی پیچیدگی زمانی (O(n log n را دارد.

سخن پایانی

در این راهنما، یک پیاده‌سازی از هیپ دودویی و مرتب‌سازی هیپ را مورد برسی قرار دادیم. با این که پیچیدگی زمانی آن در اغلب موارد (O(n log n است، اما بهترین الگوریتم در دنیای واقعی محسوب نمی‌شود.

فیلم مجموعه آموزش جاوا Java – مقدماتی تا پیشرفته در فرادرس

کلیک کنید

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های برنامه‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های دروس علوم و مهندسی کامپیوتر
• ساختمان هیپ در درخت های دودویی — به زبان ساده
• درخت هیپ (Heap) و کاربردهای آن — به زبان ساده
• توضیح الگوریتم مرتب سازی تعویضی و پیاده سازی آن در زبان های مختلف

==