Apa itu Heap?
Heap adalah struktur data berbasis pohon yang memenuhi sifat heap. Sifat heap menyatakan bahwa untuk setiap node didalam heap, nilai node tersebut lebih besar dari atau sama dengan (untuk max heap) atau kurang dari atau sama dengan (untuk min heap) nilai anak-anaknya.
Notes
- Heap dibagi menjadi dua jenis: Max heap dan Min heap. Max heap memiliki nilai terbesar di bagian atas, sedangkan Min heap memiliki nilai terkecil di bagian atas.
- Insert dan delete elemen pada heap hanya dilakukan pada root heap, karena hanya root yang berpengaruh pada sifat heap.
Ilustrasi
 |  |
Berikut merupakan contoh proses membuat array menjadi Max Heap,
Pada ilustrasi di sebelah kiri, ada tree yang sudah dibuat berdasarkan array kita, index pada tiap node ditulis sesuai array pada ilustrasi sebelumnya.
Ilustrasi sebelah kanan, menggambarkan bahwa kita akan mulai dari index di tengah ( SIZE / 2 + 1 ) yaitu index 2, untuk melihat apakah anak-anak dari node tersebut mempunyai angka yang lebih besar dari node yang sekarang kita cek.
 |  |
Ternyata benar bahwa angka dibawah node 2 adalah 5 dimana nilainya lebih besar dari node 2, kita akan menukar tempat kedua node tersebut agar property heap terpenuhi (node diatas harus lebih besar dibanding anak-anaknya)
Kita lanjutkan prosesnya, yaitu ke index 1, menurun dari sebelumnya kita cek index 2, ternyata node tersebut tidak mempunyai anak yang lebih besar valuenya, maka kita tidak akan melakukan apa-apa.
Proses selanjutnya, di index terakhir yaitu 0, kita lihat bahwa anaknya mempunyai value yang lebih besar yaitu 8, maka kita tukar kedua node tersebut.
 |  |
Jika kita menukar node, kita akan melakukan proses rekursif ke node dibawahnya lagi, oleh karena itu, kita lihat bahwa node dengan value 3 dan 4 dibawah tertukar posisinya, kita lakukan proses pindah tempat lagi.
Jadilah sebuah heap dengan value tertinggi pada root node (node paling atas)!
Implementasi
#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP_SIZE 100
// Heap
typedef struct heap {
int size;
int arr[MAX_HEAP_SIZE];
} heap;
// Utility function to swap two elements in the heap
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Utility function to maintain the max-heap property after deleting the root node
void max_heapify(heap *h, int i) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int largest = i;
if (l < h->size && h->arr[l] > h->arr[largest]) {
largest = l;
}
if (r < h->size && h->arr[r] > h->arr[largest]) {
largest = r;
}
if (largest != i) {
swap(&h->arr[i], &h->arr[largest]);
max_heapify(h, largest);
}
}
// Utility function to build a max-heap from an array
void build_max_heap(heap *h, int *arr, int n) {
h->size = n;
for (int i = 0; i < n; i++) {
h->arr[i] = arr[i];
}
for (int i = h->size / 2 - 1; i >= 0; i--) {
max_heapify(h, i);
}
}
// Utility function to insert an element into the heap
void heap_insert(heap *h, int key) {
if (h->size == MAX_HEAP_SIZE) {
printf("Error: heap overflow!\n");
return;
}
int i = h->size++;
h->arr[i] = key;
while (i > 0 && h->arr[(i - 1) / 2] < h->arr[i]) {
swap(&h->arr[i], &h->arr[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
int heap_max(heap *h) {
return h->arr[0];
}
// Utility function to delete the root node (maximum element) from the heap
int heap_delete(heap *h) {
if (h->size == 0) {
printf("Error: heap underflow!\n");
return -1;
}
int max = h->arr[0];
h->arr[0] = h->arr[--h->size];
max_heapify(h, 0);
return max;
}
// Utility function to print the contents of the heap
void print_heap(heap *h) {
printf("Heap contents: ");
for (int i = 0; i < h->size; i++) {
printf("%d ", h->arr[i]);
}
printf("\n");
}
// Main function
int main() {
heap h;
int arr[] = {12, 11, 13, 5, 6, 7};
build_max_heap(&h, arr, 6);
print_heap(&h);
heap_insert(&h, 10);
print_heap(&h);
int max = heap_max(&h);
printf("Max element: %d\n", max);
heap_delete(&h);
printf("After delete max element\n");
print_heap(&h);
return 0;
}Output
Heap contents: 13 11 12 5 6 7
Heap contents: 13 11 12 5 6 7 10
Max element: 13
After delete max element
Heap contents: 12 11 10 5 6 7