Urutan Heap di Java

1. Perkenalan

Dalam tutorial ini, kita akan melihat cara kerja Heap Sort, dan kita akan menerapkannya di Java.

Urutan Heap didasarkan pada struktur data Heap. Untuk memahami Heap Sort dengan benar, pertama-tama kita akan menggali Heap dan bagaimana penerapannya.

2. Struktur Data Heap

Heap adalah struktur data berbasis pohon khusus . Oleh karena itu, ini terdiri dari node. Kami menetapkan elemen ke node: setiap node berisi tepat satu elemen.

Selain itu, node dapat memiliki turunan. Jika simpul tidak memiliki anak, kami menyebutnya daun.

Apa yang membuat Heap spesial adalah dua hal:

  1. setiap nilai node harus kurang atau sama dengan semua nilai yang disimpan pada turunannya
  2. Ini adalah pohon yang lengkap , yang berarti pohon tersebut memiliki ketinggian yang paling sedikit

Karena aturan pertama, elemen terkecil akan selalu berada di akar pohon .

Bagaimana kami menegakkan aturan ini bergantung pada implementasi.

Heaps biasanya digunakan untuk mengimplementasikan antrian prioritas karena Heap adalah implementasi yang sangat efisien untuk mengekstraksi elemen terkecil (atau terbesar).

2.1. Varian Heap

Heap memiliki banyak varian, semuanya berbeda dalam beberapa detail penerapan.

Misalnya, apa yang kami jelaskan di atas adalah Min-Heap, karena orang tua selalu lebih kecil dari semua anaknya . Alternatifnya, kita bisa mendefinisikan Max-Heap, dalam hal ini orang tua selalu lebih besar daripada anaknya. Oleh karena itu, elemen terbesar akan berada di simpul akar.

Kita dapat memilih dari banyak implementasi pohon. Yang paling mudah adalah Pohon Biner. Dalam Pohon Biner, setiap node dapat memiliki paling banyak dua anak. Kami menyebutnya anak kiri dan anak kanan .

Cara termudah untuk menegakkan aturan ke-2 adalah dengan menggunakan Pohon Biner Penuh. Pohon Biner Lengkap mengikuti beberapa aturan sederhana:

  1. jika sebuah node hanya memiliki satu anak, itu seharusnya adalah anak kirinya
  2. hanya simpul paling kanan di tingkat terdalam yang dapat memiliki tepat satu anak
  3. daun hanya bisa berada di tingkat yang paling dalam

Mari kita lihat aturan ini dengan beberapa contoh:

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

Pohon 1, 2, 4, 5 dan 7 mengikuti aturan.

Pohon 3 dan 6 melanggar aturan ke-1, 8 dan 9 melanggar aturan ke-2, dan 10 melanggar aturan ke-3.

Dalam tutorial ini, kita akan fokus pada Min-Heap dengan implementasi Binary Tree .

2.2. Memasukkan Elemen

Kita harus menerapkan semua operasi dengan cara yang menjaga agar Heap tidak berubah. Dengan cara ini, kita bisa membangun Heap dengan penyisipan berulang , jadi kita akan fokus pada operasi penyisipan tunggal.

Kami dapat memasukkan elemen dengan langkah-langkah berikut:

  1. buat daun baru yang merupakan slot paling kanan yang tersedia di tingkat terdalam dan simpan item di simpul itu
  2. jika elemennya kurang dari induknya, kami menukarnya
  3. lanjutkan dengan langkah 2, hingga elemen kurang dari induknya atau menjadi root baru

Perhatikan, langkah 2 itu tidak akan melanggar aturan Heap, karena jika kita mengganti nilai node dengan yang lebih kecil, nilainya tetap akan lebih kecil dari anak-anaknya.

Mari kita lihat contohnya! Kami ingin memasukkan 4 ke dalam Heap ini:

 2 / \ / \ 3 6 / \ 5 7

Langkah pertama adalah membuat daun baru yang menyimpan 4:

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

Karena 4 lebih kecil dari induknya, 6, kami menukarnya:

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

Sekarang kita periksa apakah 4 kurang dari induknya atau tidak. Karena induknya adalah 2, kami berhenti. Heap masih valid, dan kami memasukkan nomor 4.

Mari masukkan 1:

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

Kami harus menukar 1 dan 4:

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

Sekarang kita harus menukar 1 dan 2:

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

Karena 1 adalah root baru, kami berhenti.

3. Implementasi Heap di Java

Karena kita menggunakan Pohon Biner Penuh, kita dapat mengimplementasikannya dengan array : elemen dalam array akan menjadi simpul di pohon. Kami menandai setiap node dengan indeks array dari kiri ke kanan, dari atas ke bawah dengan cara berikut:

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

Satu-satunya hal yang kita butuhkan adalah melacak berapa banyak elemen yang kita simpan di pohon. Dengan cara ini indeks elemen berikutnya yang ingin kita masukkan akan menjadi ukuran array.

Dengan menggunakan pengindeksan ini, kita dapat menghitung indeks node induk dan anak:

  • induk: (indeks - 1) / 2
  • left child: 2 * index + 1
  • right child: 2 * index + 2

Since we don't want to bother with array reallocating, we'll simplify the implementation even more and use an ArrayList.

A basic Binary Tree implementation looks like this:

class BinaryTree { List elements = new ArrayList(); void add(E e) { elements.add(e); } boolean isEmpty() { return elements.isEmpty(); } E elementAt(int index) { return elements.get(index); } int parentIndex(int index) { return (index - 1) / 2; } int leftChildIndex(int index) { return 2 * index + 1; } int rightChildIndex(int index) { return 2 * index + 2; } }

The code above only adds the new element to the end of the tree. Therefore, we need to traverse the new element up if necessary. We can do it with the following code:

class Heap
    
      { // ... void add(E e) { elements.add(e); int elementIndex = elements.size() - 1; while (!isRoot(elementIndex) && !isCorrectChild(elementIndex)) { int parentIndex = parentIndex(elementIndex); swap(elementIndex, parentIndex); elementIndex = parentIndex; } } boolean isRoot(int index) { return index == 0; } boolean isCorrectChild(int index) { return isCorrect(parentIndex(index), index); } boolean isCorrect(int parentIndex, int childIndex) { if (!isValidIndex(parentIndex) || !isValidIndex(childIndex)) { return true; } return elementAt(parentIndex).compareTo(elementAt(childIndex)) < 0; } boolean isValidIndex(int index) { return index < elements.size(); } void swap(int index1, int index2) { E element1 = elementAt(index1); E element2 = elementAt(index2); elements.set(index1, element2); elements.set(index2, element1); } // ... }
    

Note, that since we need to compare the elements, they need to implement java.util.Comparable.

4. Heap Sort

Since the root of the Heap always contains the smallest element, the idea behind Heap Sort is pretty simple: remove the root node until the Heap becomes empty.

The only thing we need is a remove operation, which keeps the Heap in a consistent state. We must ensure that we don't violate the structure of the Binary Tree or the Heap property.

To keep the structure, we can't delete any element, except the rightmost leaf. So the idea is to remove the element from the root node and store the rightmost leaf in the root node.

But this operation will most certainly violate the Heap property. So if the new root is greater than any of its child nodes, we swap it with its least child node. Since the least child node is less than all other child nodes, it doesn't violate the Heap property.

We keep swapping until the element becomes a leaf, or it's less than all of its children.

Let's delete the root from this tree:

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

First, we place the last leaf in the root:

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

Then, since it's greater than both of its children, we swap it with its least child, which is 2:

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

4 is less than 6, so we stop.

5. Heap Sort Implementation in Java

With all we have, removing the root (popping) looks like this:

class Heap
    
      { // ... E pop() { if (isEmpty()) { throw new IllegalStateException("You cannot pop from an empty heap"); } E result = elementAt(0); int lasElementIndex = elements.size() - 1; swap(0, lasElementIndex); elements.remove(lasElementIndex); int elementIndex = 0; while (!isLeaf(elementIndex) && !isCorrectParent(elementIndex)) { int smallerChildIndex = smallerChildIndex(elementIndex); swap(elementIndex, smallerChildIndex); elementIndex = smallerChildIndex; } return result; } boolean isLeaf(int index) { return !isValidIndex(leftChildIndex(index)); } boolean isCorrectParent(int index) { return isCorrect(index, leftChildIndex(index)) && isCorrect(index, rightChildIndex(index)); } int smallerChildIndex(int index) { int leftChildIndex = leftChildIndex(index); int rightChildIndex = rightChildIndex(index); if (!isValidIndex(rightChildIndex)) { return leftChildIndex; } if (elementAt(leftChildIndex).compareTo(elementAt(rightChildIndex)) < 0) { return leftChildIndex; } return rightChildIndex; } // ... }
    

Like we said before, sorting is just creating a Heap, and removing the root repeatedly:

class Heap
    
      { // ... static 
     
       List sort(Iterable elements) { Heap heap = of(elements); List result = new ArrayList(); while (!heap.isEmpty()) { result.add(heap.pop()); } return result; } static 
      
        Heap of(Iterable elements) { Heap result = new Heap(); for (E element : elements) { result.add(element); } return result; } // ... }
      
     
    

We can verify it's working with the following test:

@Test void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList() { // given List elements = Arrays.asList(3, 5, 1, 4, 2); // when List sortedElements = Heap.sort(elements); // then assertThat(sortedElements).isEqualTo(Arrays.asList(1, 2, 3, 4, 5)); }

Note, that we could provide an implementation, which sorts in-place, which means we provide the result in the same array we got the elements. Additionally, this way we don't need any intermediate memory allocation. However, that implementation would be a bit harder to understand.

6. Time Complexity

Heap sort consists of two key steps, inserting an element and removing the root node. Both steps have the complexity O(log n).

Since we repeat both steps n times, the overall sorting complexity is O(n log n).

Note, that we didn't mention the cost of array reallocation, but since it's O(n), it doesn't affect the overall complexity. Also, as we mentioned before, it's possible to implement an in-place sorting, which means no array reallocation is necessary.

Also worth mentioning, that 50% of the elements are leaves, and 75% of elements are at the two bottommost levels. Therefore, most insert operations won't take more, than two steps.

Perhatikan, bahwa pada data dunia nyata, Quicksort biasanya lebih berkinerja daripada Heap Sort. Hal terpenting adalah Heap Sort selalu memiliki kompleksitas waktu O (n log n) kasus terburuk .

7. Kesimpulan

Dalam tutorial ini, kami melihat implementasi dari Binary Heap dan Heap Sort.

Meskipun kompleksitas waktunya adalah O (n log n) , dalam banyak kasus, ini bukan algoritme terbaik pada data dunia nyata.

Seperti biasa, contoh tersedia di GitHub.