Struktur Data Paling Berguna untuk LeetCode: Panduan Komprehensif

LeetCode adalah platform luar biasa untuk mengasah keterampilan algoritma dan struktur data Anda. Penguasaan struktur data sangat penting untuk memecahkan berbagai masalah LeetCode secara efisien. Artikel ini akan membahas struktur data yang paling berguna yang perlu Anda kuasai untuk sukses di LeetCode, memberikan penjelasan mendalam, contoh kode, dan petunjuk tentang kapan menggunakan masing-masing struktur.

Mengapa Struktur Data Penting untuk LeetCode?

Sebelum kita membahas struktur data tertentu, mari kita pahami mengapa mereka sangat penting untuk LeetCode:

• Efisiensi: Struktur data yang dipilih secara tepat dapat secara signifikan mengurangi kompleksitas waktu dan ruang solusi Anda.
• Kejelasan Kode: Menggunakan struktur data yang sesuai dapat membuat kode Anda lebih mudah dibaca, dipelihara, dan dipahami.
• Pemecahan Masalah: Banyak masalah LeetCode secara alami meminjamkan diri pada struktur data tertentu. Mengenali pola-pola ini akan menyederhanakan proses pemecahan masalah.
• Persiapan Wawancara: Menguasai struktur data adalah keterampilan penting yang sering dievaluasi dalam wawancara teknis.

Kerangka Posting Blog: Struktur Data Utama untuk LeetCode

1. Pendahuluan
   • Pentingnya Struktur Data untuk LeetCode
   • Tujuan artikel: Menjelaskan struktur data yang paling berguna dan kapan menggunakannya
2. Array
   • Definisi dan karakteristik dasar
   • Operasi umum (akses, penyisipan, penghapusan) dan kompleksitas waktunya
   • Masalah LeetCode yang cocok:
     • Dua Jumlah
     • Array yang Diputar
     • Maximum Subarray
   • Tips dan Trik untuk Memecahkan Masalah Array
3. Linked List
   • Definisi dan jenis (single, double, circular)
   • Operasi umum (penyisipan, penghapusan, traversal) dan kompleksitas waktunya
   • Masalah LeetCode yang cocok:
     • Balikkan Linked List
     • Deteksi Siklus di Linked List
     • Gabungkan Dua Sorted List
   • Tips dan Trik untuk Memecahkan Masalah Linked List
4. Stack
   • Definisi dan prinsip LIFO (Last-In, First-Out)
   • Operasi umum (push, pop, peek) dan kompleksitas waktunya
   • Masalah LeetCode yang cocok:
     • Valid Parentheses
     • Evaluasi Ekspresi
     • Next Greater Element
   • Tips dan Trik untuk Memecahkan Masalah Stack
5. Queue
   • Definisi dan prinsip FIFO (First-In, First-Out)
   • Operasi umum (enqueue, dequeue, peek) dan kompleksitas waktunya
   • Jenis antrian (antrian prioritas, deque)
   • Masalah LeetCode yang cocok:
     • Implementasikan Queue menggunakan Stacks
     • Level Order Traversal Binary Tree
     • Sliding Window Maximum
   • Tips dan Trik untuk Memecahkan Masalah Queue
6. Hash Table (Hash Map)
   • Definisi, tujuan, dan cara kerja
   • Operasi umum (penyisipan, penghapusan, pencarian) dan kompleksitas waktunya
   • Resolusi bentrokan (chaining, open addressing)
   • Masalah LeetCode yang cocok:
     • Dua Jumlah
     • Anagram Grup
     • Panjang Substring Terpanjang Tanpa Karakter Berulang
   • Tips dan Trik untuk Memecahkan Masalah Hash Table
7. Tree
   • Definisi dan jenis (binary tree, binary search tree, trie)
   • Traversal pohon (inorder, preorder, postorder, level order)
   • Operasi umum (penyisipan, penghapusan, pencarian) dan kompleksitas waktunya
   • Masalah LeetCode yang cocok:
     • Maximum Depth of Binary Tree
     • Valid Binary Search Tree
     • Implementasikan Trie (Prefix Tree)
   • Tips dan Trik untuk Memecahkan Masalah Tree
8. Graph
   • Definisi dan representasi (adjacency list, adjacency matrix)
   • Algoritma graph umum (BFS, DFS)
   • Masalah LeetCode yang cocok:
     • Number of Islands
     • Course Schedule
     • Clone Graph
   • Tips dan Trik untuk Memecahkan Masalah Graph
9. Heap (Priority Queue)
   • Definisi dan jenis (min heap, max heap)
   • Operasi umum (penyisipan, penghapusan, peek) dan kompleksitas waktunya
   • Implementasi heap menggunakan array
   • Masalah LeetCode yang cocok:
     • Kth Largest Element in an Array
     • Merge K Sorted Lists
     • Top K Frequent Elements
   • Tips dan Trik untuk Memecahkan Masalah Heap
10. Kesimpulan
    • Ringkasan struktur data utama yang dibahas
    • Dorongan untuk berlatih dan menjelajahi struktur data lebih lanjut

1. Array

Array adalah struktur data mendasar yang menyimpan kumpulan elemen dengan tipe data yang sama di lokasi memori yang berdekatan. Elemen-elemen ini dapat diakses menggunakan indeks, dimulai dari 0.

• Definisi: Kumpulan elemen dengan tipe data yang sama, disimpan dalam lokasi memori yang berdekatan.
• Karakteristik:
  • Akses acak: Elemen dapat diakses langsung menggunakan indeksnya.
  • Ukuran tetap: Ukuran array biasanya tetap setelah dibuat (dalam array statis). Array dinamis (seperti ArrayList di Java atau list di Python) dapat berubah ukurannya.
  • Tipe data homogen: Semua elemen harus dari tipe data yang sama.

Operasi Array Umum dan Kompleksitas Waktu

1. Akses: Mengakses elemen pada indeks tertentu.
   • Kompleksitas Waktu: O(1)
2. Penyisipan: Menyisipkan elemen pada indeks tertentu.
   • Kompleksitas Waktu: O(n) dalam kasus terburuk (membutuhkan pergeseran elemen untuk membuat ruang). Dalam array dinamis, penyisipan di akhir bisa O(1) (amortisasi).
3. Penghapusan: Menghapus elemen pada indeks tertentu.
   • Kompleksitas Waktu: O(n) dalam kasus terburuk (membutuhkan pergeseran elemen untuk mengisi celah). Dalam array dinamis, penghapusan di akhir bisa O(1) (amortisasi).
4. Pencarian: Mencari elemen tertentu.
   • Kompleksitas Waktu: O(n) untuk pencarian linear. O(log n) jika array diurutkan (menggunakan pencarian biner).

Masalah LeetCode yang Cocok untuk Array

1. Dua Jumlah (Two Sum): Temukan dua angka dalam array yang jumlahnya sama dengan target tertentu.
   • Pendekatan: Gunakan hash table untuk menyimpan angka yang sudah dilihat dan periksa apakah komplemen (target – angka saat ini) ada di hash table.
   • Contoh Kode (Python):

             
   def twoSum(nums, target):
     numMap = {}
     for i, num in enumerate(nums):
       complement = target - num
       if complement in numMap:
         return [numMap[complement], i]
       else:
         numMap[num] = i
     return [] # No solution found
             
           

2. Array yang Diputar (Rotated Array): Cari elemen dalam array yang diputar.
   • Pendekatan: Gunakan pencarian biner yang dimodifikasi untuk mengakomodasi putaran.
3. Maximum Subarray: Temukan jumlah subarray maksimum dalam array.
   • Pendekatan: Gunakan algoritma Kadane.
   • Contoh Kode (Python):

             
   def maxSubArray(nums):
     max_so_far = nums[0]
     current_max = nums[0]
   
     for i in range(1, len(nums)):
       current_max = max(nums[i], current_max + nums[i])
       max_so_far = max(max_so_far, current_max)
   
     return max_so_far
             
           

Tips dan Trik untuk Memecahkan Masalah Array

• Memahami Kendala: Perhatikan kendala ukuran array dan rentang nilai elemen. Ini akan membantu Anda memilih algoritma dan struktur data yang sesuai.
• Dua Penunjuk: Teknik dua penunjuk sangat berguna untuk memecahkan masalah yang melibatkan array yang diurutkan atau yang perlu membandingkan elemen.
• Pencarian Biner: Pencarian biner adalah teknik yang kuat untuk mencari elemen dalam array yang diurutkan dalam waktu logaritmik.
• Sliding Window: Teknik sliding window berguna untuk memecahkan masalah yang melibatkan pencarian subarray atau substring dengan panjang tertentu yang memenuhi kondisi tertentu.
• Prefix Sum: Prefix sum dapat membantu memecahkan masalah yang melibatkan menghitung jumlah elemen dalam rentang tertentu secara efisien.

2. Linked List

Linked List adalah struktur data linear di mana elemen tidak disimpan di lokasi memori yang berdekatan. Sebaliknya, setiap elemen (disebut node) berisi data dan penunjuk ke node berikutnya dalam urutan.

• Definisi: Kumpulan node, di mana setiap node berisi data dan penunjuk ke node berikutnya.
• Jenis:
  • Singly Linked List: Setiap node menunjuk ke node berikutnya.
  • Doubly Linked List: Setiap node menunjuk ke node berikutnya dan node sebelumnya.
  • Circular Linked List: Node terakhir menunjuk ke node pertama.

Operasi Linked List Umum dan Kompleksitas Waktu

1. Penyisipan: Menyisipkan node pada posisi tertentu.
   • Kompleksitas Waktu: O(1) jika Anda memiliki penunjuk ke node sebelumnya. O(n) jika Anda perlu mencari posisi untuk menyisipkan.
2. Penghapusan: Menghapus node dari posisi tertentu.
   • Kompleksitas Waktu: O(1) jika Anda memiliki penunjuk ke node sebelumnya. O(n) jika Anda perlu mencari node yang akan dihapus.
3. Traversal: Mengunjungi setiap node dalam daftar.
   • Kompleksitas Waktu: O(n)
4. Pencarian: Mencari node dengan nilai tertentu.
   • Kompleksitas Waktu: O(n)

Masalah LeetCode yang Cocok untuk Linked List

1. Balikkan Linked List (Reverse Linked List): Balikkan urutan node dalam linked list.
   • Pendekatan: Gunakan tiga penunjuk: previous, current, dan next.
   • Contoh Kode (Python):

             
   def reverseList(head):
     prev = None
     curr = head
     while curr:
       next_node = curr.next
       curr.next = prev
       prev = curr
       curr = next_node
     return prev
             
           

2. Deteksi Siklus di Linked List (Linked List Cycle): Deteksi apakah linked list memiliki siklus.
   • Pendekatan: Gunakan algoritma Floyd’s Cycle-Finding (penunjuk kura-kura dan kelinci).
3. Gabungkan Dua Sorted List (Merge Two Sorted Lists): Gabungkan dua linked list yang diurutkan menjadi satu linked list yang diurutkan.
   • Pendekatan: Rekursif atau iteratif.

Tips dan Trik untuk Memecahkan Masalah Linked List

• Dummy Node: Gunakan dummy node untuk menyederhanakan operasi penyisipan dan penghapusan, terutama di kepala daftar.
• Dua Penunjuk: Teknik dua penunjuk sangat berguna untuk masalah seperti menemukan node tengah, mendeteksi siklus, atau membalikkan daftar.
• Rekursi: Rekursi dapat menjadi cara yang elegan untuk memecahkan masalah linked list, terutama yang melibatkan operasi pada sublist.
• Visualisasi: Gambarkan linked list dan operasinya untuk membantu Anda memahami logika dan menghindari kesalahan.

3. Stack

Stack adalah struktur data linear yang mengikuti prinsip LIFO (Last-In, First-Out). Elemen ditambahkan dan dihapus hanya dari satu ujung, yang disebut “top”.

• Definisi: Struktur data yang mengikuti prinsip LIFO (Last-In, First-Out).
• Operasi:
  • Push: Menambahkan elemen ke top stack.
  • Pop: Menghapus elemen dari top stack.
  • Peek: Melihat elemen di top stack tanpa menghapusnya.

Operasi Stack Umum dan Kompleksitas Waktu

1. Push: Menambahkan elemen ke top stack.
   • Kompleksitas Waktu: O(1)
2. Pop: Menghapus elemen dari top stack.
   • Kompleksitas Waktu: O(1)
3. Peek: Melihat elemen di top stack tanpa menghapusnya.
   • Kompleksitas Waktu: O(1)
4. IsEmpty: Memeriksa apakah stack kosong.
   • Kompleksitas Waktu: O(1)

Masalah LeetCode yang Cocok untuk Stack

1. Valid Parentheses: Periksa apakah string tanda kurung valid (misalnya, “(){}[]” valid, tetapi “([)]” tidak valid).
   • Pendekatan: Gunakan stack untuk mencocokkan tanda kurung pembuka dan penutup.
   • Contoh Kode (Python):

             
   def isValid(s):
     stack = []
     mapping = {")": "(", "}": "{", "]": "["}
     for char in s:
       if char in mapping:
         top_element = stack.pop() if stack else '#'
         if mapping[char] != top_element:
           return False
       else:
         stack.append(char)
     return not stack
             
           

2. Evaluasi Ekspresi (Evaluate Expression): Evaluasi ekspresi aritmatika yang diberikan dalam notasi infix atau postfix.
   • Pendekatan: Gunakan stack untuk menyimpan operand dan operator.
3. Next Greater Element: Temukan elemen lebih besar berikutnya untuk setiap elemen dalam array.
   • Pendekatan: Gunakan stack untuk melacak elemen yang belum menemukan elemen lebih besar berikutnya.

Tips dan Trik untuk Memecahkan Masalah Stack

• Memahami LIFO: Ingat prinsip LIFO stack.
• Mencocokkan: Stack sangat berguna untuk mencocokkan tanda kurung, tag HTML, atau elemen lain yang perlu dipasangkan.
• Backtracking: Stack dapat digunakan untuk backtracking dan algoritma DFS.
• Monotonic Stack: Monotonic stack (stack yang elemennya selalu naik atau turun) dapat digunakan untuk memecahkan berbagai masalah optimasi.

4. Queue

Queue adalah struktur data linear yang mengikuti prinsip FIFO (First-In, First-Out). Elemen ditambahkan di satu ujung (disebut “rear” atau “enqueue”) dan dihapus dari ujung lainnya (disebut “front” atau “dequeue”).

• Definisi: Struktur data yang mengikuti prinsip FIFO (First-In, First-Out).
• Operasi:
  • Enqueue: Menambahkan elemen ke rear queue.
  • Dequeue: Menghapus elemen dari front queue.
  • Peek: Melihat elemen di front queue tanpa menghapusnya.
• Jenis:
  • Antrian Prioritas (Priority Queue): Elemen dihapus berdasarkan prioritasnya.
  • Deque (Double-Ended Queue): Elemen dapat ditambahkan atau dihapus dari kedua ujung.

Operasi Queue Umum dan Kompleksitas Waktu

1. Enqueue: Menambahkan elemen ke rear queue.
   • Kompleksitas Waktu: O(1)
2. Dequeue: Menghapus elemen dari front queue.
   • Kompleksitas Waktu: O(1)
3. Peek: Melihat elemen di front queue tanpa menghapusnya.
   • Kompleksitas Waktu: O(1)
4. IsEmpty: Memeriksa apakah queue kosong.
   • Kompleksitas Waktu: O(1)

Masalah LeetCode yang Cocok untuk Queue

1. Implementasikan Queue menggunakan Stacks (Implement Queue using Stacks): Implementasikan queue menggunakan dua stacks.
   • Pendekatan: Gunakan satu stack untuk enqueue dan stack lainnya untuk dequeue.
2. Level Order Traversal Binary Tree (Binary Tree Level Order Traversal): Lakukan traversal level order dari binary tree.
   • Pendekatan: Gunakan queue untuk menyimpan node di setiap level.
   • Contoh Kode (Python):

             
   from collections import deque
   
   def levelOrder(root):
     if not root:
       return []
   
     queue = deque([root])
     result = []
   
     while queue:
       level_size = len(queue)
       current_level = []
       for _ in range(level_size):
         node = queue.popleft()
         current_level.append(node.val)
   
         if node.left:
           queue.append(node.left)
         if node.right:
           queue.append(node.right)
   
       result.append(current_level)
   
     return result
             
           

3. Sliding Window Maximum: Temukan maksimum sliding window dari ukuran k dalam array.
   • Pendekatan: Gunakan deque untuk menyimpan indeks elemen yang berpotensi maksimum dalam jendela.

Tips dan Trik untuk Memecahkan Masalah Queue

• Memahami FIFO: Ingat prinsip FIFO queue.
• BFS: Queue sangat berguna untuk algoritma Breadth-First Search (BFS).
• Sliding Window: Deque sangat berguna untuk masalah sliding window.
• Simulasi: Queue dapat digunakan untuk mensimulasikan proses antrian di dunia nyata.

5. Hash Table (Hash Map)

Hash Table (juga dikenal sebagai Hash Map) adalah struktur data yang menyimpan pasangan kunci-nilai. Struktur ini memungkinkan pencarian, penyisipan, dan penghapusan elemen yang efisien berdasarkan kunci.

• Definisi: Struktur data yang menyimpan pasangan kunci-nilai dan memungkinkan pencarian, penyisipan, dan penghapusan yang efisien berdasarkan kunci.
• Cara Kerja: Kunci di-hash menggunakan fungsi hash untuk menentukan indeks dalam array (disebut “table”) di mana nilai yang sesuai disimpan.
• Resolusi Bentrokan:
  • Chaining: Setiap indeks dalam table menyimpan linked list dari pasangan kunci-nilai yang memiliki indeks hash yang sama.
  • Open Addressing: Ketika terjadi bentrokan, cari indeks lain yang tersedia dalam table.

Operasi Hash Table Umum dan Kompleksitas Waktu

1. Penyisipan: Menyisipkan pasangan kunci-nilai.
   • Kompleksitas Waktu: O(1) rata-rata (asumsi fungsi hash yang baik). O(n) dalam kasus terburuk (semua kunci hash ke indeks yang sama).
2. Penghapusan: Menghapus pasangan kunci-nilai berdasarkan kunci.
   • Kompleksitas Waktu: O(1) rata-rata. O(n) dalam kasus terburuk.
3. Pencarian: Mencari nilai berdasarkan kunci.
   • Kompleksitas Waktu: O(1) rata-rata. O(n) dalam kasus terburuk.

Masalah LeetCode yang Cocok untuk Hash Table

1. Dua Jumlah (Two Sum): Temukan dua angka dalam array yang jumlahnya sama dengan target tertentu. (Seperti yang dibahas di bagian Array)
2. Anagram Grup (Group Anagrams): Kelompokkan anagram dari daftar string.
   • Pendekatan: Gunakan hash table untuk menyimpan string berdasarkan signature anagram mereka (misalnya, string yang diurutkan).
3. Panjang Substring Terpanjang Tanpa Karakter Berulang (Longest Substring Without Repeating Characters): Temukan panjang substring terpanjang tanpa karakter berulang.
   • Pendekatan: Gunakan sliding window dan hash table untuk melacak karakter yang terlihat dalam jendela saat ini.
   • Contoh Kode (Python):

             
   def lengthOfLongestSubstring(s):
     char_index_map = {}
     start = 0
     max_length = 0
   
     for end, char in enumerate(s):
       if char in char_index_map and char_index_map[char] >= start:
         start = char_index_map[char] + 1
       char_index_map[char] = end
       max_length = max(max_length, end - start + 1)
   
     return max_length
             
           

Tips dan Trik untuk Memecahkan Masalah Hash Table

• Memilih Fungsi Hash yang Baik: Fungsi hash yang baik mendistribusikan kunci secara merata untuk meminimalkan bentrokan.
• Mengelola Bentrokan: Memahami teknik resolusi bentrokan (chaining, open addressing).
• Trade-off Ruang-Waktu: Hash table menawarkan pencarian cepat dengan mengorbankan ruang memori.
• Menggunakan defaultdict: Di Python, defaultdict dari modul collections dapat menyederhanakan kode Anda saat bekerja dengan hash table.

6. Tree

Tree adalah struktur data hierarkis yang terdiri dari node yang terhubung oleh tepi. Node paling atas disebut “root”, dan node tanpa anak disebut “leaf”.

• Definisi: Struktur data hierarkis yang terdiri dari node yang terhubung oleh tepi.
• Jenis:
  • Binary Tree: Setiap node memiliki paling banyak dua anak (left child dan right child).
  • Binary Search Tree (BST): Binary tree di mana untuk setiap node, semua node di subtree kirinya memiliki nilai lebih kecil dari node, dan semua node di subtree kanannya memiliki nilai lebih besar dari node.
  • Trie (Prefix Tree): Tree yang digunakan untuk menyimpan string, di mana setiap node mewakili awalan.

Traversal Pohon

1. Inorder Traversal: Kunjungi subtree kiri, lalu node, lalu subtree kanan. (Left, Root, Right)
2. Preorder Traversal: Kunjungi node, lalu subtree kiri, lalu subtree kanan. (Root, Left, Right)
3. Postorder Traversal: Kunjungi subtree kiri, lalu subtree kanan, lalu node. (Left, Right, Root)
4. Level Order Traversal: Kunjungi node level demi level, mulai dari root. (Menggunakan Queue)

Operasi Tree Umum dan Kompleksitas Waktu

1. Penyisipan: Menyisipkan node (tergantung pada jenis tree).
   • Kompleksitas Waktu: O(log n) untuk BST rata-rata. O(n) untuk BST dalam kasus terburuk (tree miring).
2. Penghapusan: Menghapus node (tergantung pada jenis tree).
   • Kompleksitas Waktu: O(log n) untuk BST rata-rata. O(n) untuk BST dalam kasus terburuk.
3. Pencarian: Mencari node (tergantung pada jenis tree).
   • Kompleksitas Waktu: O(log n) untuk BST rata-rata. O(n) untuk BST dalam kasus terburuk.

Masalah LeetCode yang Cocok untuk Tree

1. Maximum Depth of Binary Tree: Temukan kedalaman maksimum binary tree.
   • Pendekatan: Rekursif atau iteratif (menggunakan BFS).
   • Contoh Kode (Python):

             
   def maxDepth(root):
     if not root:
       return 0
     return 1 + max(maxDepth(root.left), maxDepth(root.right))
             
           

2. Valid Binary Search Tree: Periksa apakah binary tree adalah binary search tree yang valid.
   • Pendekatan: Rekursif atau iteratif (menggunakan inorder traversal).
3. Implementasikan Trie (Prefix Tree): Implementasikan Trie dengan operasi insert, search, dan startsWith.
   • Pendekatan: Gunakan node untuk mewakili karakter, dan tepi untuk mewakili transisi antar karakter.

Tips dan Trik untuk Memecahkan Masalah Tree

• Memahami Jenis Tree: Pahami perbedaan antara jenis tree yang berbeda (binary tree, BST, trie).
• Rekursi: Rekursi adalah teknik yang ampuh untuk memecahkan masalah tree.
• Traversal Pohon: Kuasai berbagai teknik traversal pohon (inorder, preorder, postorder, level order).
• BST Properties: Manfaatkan properti BST saat bekerja dengan binary search tree.

7. Graph

Graph adalah struktur data non-linear yang terdiri dari node (vertices) yang terhubung oleh tepi (edges). Graph dapat digunakan untuk merepresentasikan berbagai hubungan, seperti jaringan sosial, peta jalan, dan dependensi perangkat lunak.

• Definisi: Struktur data non-linear yang terdiri dari node (vertices) yang terhubung oleh tepi (edges).
• Representasi:
  • Adjacency List: Representasikan graph sebagai daftar node, di mana setiap node berisi daftar tetangganya.
  • Adjacency Matrix: Representasikan graph sebagai matriks, di mana entri (i, j) menunjukkan apakah ada tepi antara node i dan node j.

Algoritma Graph Umum

1. Breadth-First Search (BFS): Traversal graph level demi level, mulai dari node sumber. Gunakan queue.
2. Depth-First Search (DFS): Traversal graph sedalam mungkin di setiap cabang sebelum backtracking. Gunakan stack (implisit melalui rekursi).

Masalah LeetCode yang Cocok untuk Graph

1. Number of Islands: Hitung jumlah pulau dalam grid biner (1 mewakili daratan, 0 mewakili air).
   • Pendekatan: Gunakan DFS atau BFS untuk menjelajahi setiap pulau.
2. Course Schedule: Tentukan apakah mungkin untuk menyelesaikan semua kursus yang diberikan dependensi prasyarat.
   • Pendekatan: Gunakan topological sort (BFS atau DFS).
3. Clone Graph: Klone graph yang diberikan.
   • Pendekatan: Gunakan DFS atau BFS untuk menjelajahi graph dan membuat salinan dari setiap node dan tepi.

Tips dan Trik untuk Memecahkan Masalah Graph

• Memilih Representasi yang Tepat: Pilih representasi graph yang sesuai (adjacency list atau adjacency matrix) berdasarkan karakteristik masalah. Adjacency list lebih efisien untuk graph yang jarang, sedangkan adjacency matrix lebih efisien untuk graph yang padat.
• Memahami BFS dan DFS: Kuasai algoritma BFS dan DFS dan pahami kapan menggunakan masing-masing.
• Track Node yang Dikunjungi: Gunakan set untuk melacak node yang telah dikunjungi untuk menghindari siklus dan infinite loop.
• Topological Sort: Pahami topological sort dan kapan menggunakannya (misalnya, untuk masalah yang melibatkan dependensi).

8. Heap (Priority Queue)

Heap (atau Priority Queue) adalah struktur data tree yang memenuhi properti heap: nilai setiap node lebih besar dari atau sama dengan (atau kurang dari atau sama dengan) nilai anaknya. Heap biasanya digunakan untuk mengimplementasikan priority queue, di mana elemen dengan prioritas tertinggi selalu dihapus terlebih dahulu.

• Definisi: Struktur data tree yang memenuhi properti heap.
• Jenis:
  • Min Heap: Nilai setiap node lebih kecil dari atau sama dengan nilai anaknya.
  • Max Heap: Nilai setiap node lebih besar dari atau sama dengan nilai anaknya.
• Implementasi: Heap biasanya diimplementasikan menggunakan array.

Operasi Heap Umum dan Kompleksitas Waktu

1. Penyisipan: Menyisipkan elemen ke heap.
   • Kompleksitas Waktu: O(log n)
2. Penghapusan: Menghapus elemen dengan prioritas tertinggi (root).
   • Kompleksitas Waktu: O(log n)
3. Peek: Melihat elemen dengan prioritas tertinggi (root).
   • Kompleksitas Waktu: O(1)

Masalah LeetCode yang Cocok untuk Heap

1. Kth Largest Element in an Array: Temukan elemen terbesar ke-k dalam array.
   • Pendekatan: Gunakan min heap untuk menyimpan k elemen terbesar yang terlihat sejauh ini.
   • Contoh Kode (Python):

             
   import heapq
   
   def findKthLargest(nums, k):
     heap = []
     for num in nums:
       heapq.heappush(heap, num)
       if len(heap) > k:
         heapq.heappop(heap)
     return heapq.heappop(heap)
             
           

2. Merge K Sorted Lists: Gabungkan k sorted linked list menjadi satu sorted linked list.
   • Pendekatan: Gunakan min heap untuk menyimpan kepala setiap linked list.
3. Top K Frequent Elements: Temukan k elemen yang paling sering dalam array.
   • Pendekatan: Gunakan hash table untuk menghitung frekuensi setiap elemen, lalu gunakan min heap untuk menyimpan k elemen yang paling sering.

Tips dan Trik untuk Memecahkan Masalah Heap

• Memahami Properti Heap: Pahami properti min heap dan max heap.
• Menggunakan heapq Module: Di Python, gunakan modul heapq untuk mengimplementasikan heap.
• Prioritas: Heap berguna ketika Anda perlu memproses elemen berdasarkan prioritasnya.
• Kompleksitas Waktu: Ingat kompleksitas waktu operasi heap.

9. Kesimpulan