- Heap adalah complete binary tree (bukan binary
search tree) yang mempunyai properties sebagai berikut:
•
Min Heap:
-
Setiap node lebih kecil daripada child
•
Max Heap:
-
Setiap node lebis besar daripada child
· Min Heap :
- Setiap node lebih kecil dari
masing-masing childnya
- Root merupakan node paling kecil,
sedangkan node terbesar terletak pada leaf node
•
Upheap in Min-Heap:
-Bandingkan nilai node saat ini (mulai dengan node yang disisipkan)
dengan nilai parent. Jika nilai node saat ini lebih kecil dari nilai parent
daripada menukar nilainya dan teruskan upheap node induknya.
-Berhenti jika nilai parent lebih kecil dari nilai simpul
saat ini atau node saat ini adalah root (tidak memiliki induk).
•
Downheap in Min-Heap :
-Bandingkan nilai node saat ini (mulai dengan root) dengan
nilai anak kiri dan kanannya. Tukar simpul saat ini dengan child terkecil dan
lanjutkan downheap pada simpul (child) itu.
-Berhenti jika nilai simpul saat ini lebih kecil dari nilai child
atau node saat ini adalah daun (tidak memiliki child).
· Max Heap :
- Setiap node lebih besar dari
masing-masing childnya
- Root merupakan node paling besar,
sedangkan node terkecil terletak pada leaf node
Heap adalah implementasi efisien dari struktur data antrian
prioritas.
1 .
find-min: cari elemen terkecil di heap.
2 .
insertion: masukkan elemen baru ke heap.
3 .
delete-min: hapus elemen terkecil dari heap.
(delete-min juga disebut pop, dan masukkan
disebut push.)
- Heaps biasanya diimplementasikan dalam sebuah array.
- Elemen-elemen disimpan secara berurutan dari indeks 1 ke N dari atas ke bawah dan dari node kiri ke kanan tree.
- Root disimpan dalam indeks 1
(kami membiarkan indeks 0 kosong / tidak digunakan, untuk
tujuan kenyamanan).
• - Biarkan indeks simpul saat ini menjadi x.
• - Setiap hubungan node dengan parents, left child
dan right child dalam implementasi array dapat dihitung dengan mudah
- Parents (x) = x / 2
- Left Child (x) = 2 * x
- Right Child (x) = 2 * x + 1
Inilah mengapa menggunakan indeks 1 sebagai root, jika tidak
hubungan tidak akan muncul sesederhana ini.
Contoh Coding Insertion and Delete
Delete :
#include <iostream>
using namespace std;
// To heapify a subtree rooted with
node i which is
// an index in arr[]. N is size of
heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left
child is larger than root
if (l < n && arr[l] > arr[largest])
largest
= l;
// If right
child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest
= r;
// If
largest is not root
if (largest != i) {
swap(arr[i],
arr[largest]);
//
Recursively heapify the affected sub-tree
heapify(arr,
n, largest);
}
}
// Function to delete the root from
Heap
void deleteRoot(int arr[], int& n)
{
// Get the
last element
int lastElement = arr[n - 1];
// Replace
root with first element
arr[0] =
lastElement;
// Decrease
size of heap by 1
n = n - 1;
// heapify
the root node
heapify(arr,
n, 0);
}
/* A utility function to print array
of size n */
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout
<< arr[i] << " ";
cout
<< "\n";
}
// Driver Code
int main()
{
// Array
representation of Max-Heap
// 10
//
/ \
//
5 3
// / \
//
2 4
int arr[] = { 10, 5, 3, 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
deleteRoot(arr,
n);
printArray(arr,
n);
return 0;
}
Insertion :
#include <iostream>
using namespace std;
#define MAX 1000 // Max size of Heap
// Function to heapify ith node in a
Heap
// of size n following a Bottom-up
approach
void heapify(int arr[], int n, int i)
{
// Find
parent
int parent = (i - 1) / 2;
if (arr[parent] > 0) {
//
For Max-Heap
//
If current node is greater than its parent
//
Swap both of them and call heapify again
//
for the parent
if (arr[i] > arr[parent]) {
swap(arr[i],
arr[parent]);
//
Recursively heapify the parent node
heapify(arr,
n, parent);
}
}
}
// Function to insert a new node to
the Heap
void insertNode(int arr[], int& n, int Key)
{
// Increase
the size of Heap by 1
n = n + 1;
// Insert
the element at end of Heap
arr[n - 1] =
Key;
// Heapify
the new node following a
// Bottom-up
approach
heapify(arr,
n, n - 1);
}
// A utility function to print array
of size n
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout
<< arr[i] << " ";
cout
<< "\n";
}
// Driver Code
int main()
{
// Array
representation of Max-Heap
// 10
//
/ \
//
5 3
// / \
//
2 4
int arr[MAX] = { 10, 5, 3, 2, 4 };
int n = 5;
int key = 15;
insertNode(arr,
n, key);
printArray(arr,
n);
// Final
Heap will be:
// 15
//
/ \
//
5 10
// /
\ /
//
2 4 3
return 0;
}
Min – Max Heap :
•
Kondisi tumpukan bergantian antara level minimum
dan maksimum ke level
-Setiap elemen pada level genap / ganjil lebih kecil dari
semua anak-anaknya (level min).
-Setiap elemen pada level ganjil / genap lebih besar dari
semua anak-anaknya (level maksimal).
- Tujuan dari tumpukan minimum adalah untuk memungkinkan kami menemukan elemen tumpukan terkecil dan terbesar sekaligus.
- Dalam tumpukan minimum,
-
Elemen terkecil terletak di root.
-
Elemen terbesar terletak di salah satu anak root
(baik anak kiri / kanan).
Catatan: elemen terbesar mungkin terletak di root jika hanya
ada satu elemen di heap.
•
- Upheap in Min-Max Heap
•
Jika node baru berada pada level min
- Jika induk node baru lebih kecil dari itu, maka tukarkan
nilainya dan upheapmax dari parents.
- Selain itu upheapmin dari node baru
•
Jika node baru berada pada level maksimal
-Jika parent node baru lebih besar dari itu, maka tukar
nilainya dan upheapmin dari parent.
-Selain itu upheapmax
dari node baru
• - Upheapmin
Bandingkan nilai node saat ini dengan nilai
grand-parent-nya. Jika nilai node saat ini lebih kecil dari nilai induknya maka
tukar nilai-nilai mereka dan teruskan upheap min grand-parent.
• - Upheapmax
Bandingkan nilai node saat ini dengan nilai
grand-parent-nya. Jika nilai node saat ini lebih besar dari nilai parent maka
tukar nilai-nilai mereka dan teruskan upheap max grand-parent.
Tries :
Tries (prefix tree) adalah struktur data tree terurut yang
digunakan untuk menyimpan array asosiatif (biasanya string)
Istilah TRIE berasal dari kata RETRIEVAL, karena mencoba
dapat menemukan satu kata dalam kamus dengan hanya awalan kata.
