maxheap

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
};

// Membuat node baru
Node* createNode(int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Swap nilai antara dua node
void swapValues(Node* a, Node* b) {
    int temp = a->data;
    a->data = b->data;
    b->data = temp;
}

// Mendapatkan tinggi tree
int getHeight(Node* root) {
    if (!root) return 0;
    return 1 + max(getHeight(root->left), getHeight(root->right));
}

// Cek apakah node pada level tertentu sudah penuh
bool isLevelFull(Node* root, int level) {
    if (!root) return false;
    if (level == 1) return root->left && root->right;
    return isLevelFull(root->left, level-1) && isLevelFull(root->right, level-1);
}

// Heapify untuk menjaga properti max heap
void heapify(Node* root) {
    if (!root) return;
    
    Node* largest = root;
    Node* left = root->left;
    Node* right = root->right;
    
    if (left && left->data > largest->data)
        largest = left;
        
    if (right && right->data > largest->data)
        largest = right;
        
    if (largest != root) {
        swapValues(root, largest);
        heapify(largest);
    }
}

// Insert dengan pengecekan level
// Jika root kosong, buat node baru
// Jika nilai baru lebih besar dari root, tukar nilainya
// Cek tinggi tree saat ini
// Untuk setiap level:
    // Cek apakah level tersebut sudah penuh
    // Jika belum penuh, isi dari kiri ke kanan
    // Jika sudah penuh, lanjut ke level berikutnya
    // Pilih subtree yang lebih pendek untuk menjaga keseimbangan complete tree
Node* insert(Node* root, int value, int level = 1) {
    // Jika root kosong, buat node baru
    if (!root) return createNode(value);
    
    // Jika nilai baru lebih besar, tukar dengan root
    if (value > root->data) {
        int temp = root->data;
        root->data = value;
        value = temp;
    }
    
    int height = getHeight(root);
    
    // Jika di level saat ini masih ada tempat
    if (level <= height) {
        // Jika level sebelumnya belum penuh, isi level tersebut dulu
        if (!isLevelFull(root, level)) {
            // Prioritaskan left child jika kosong
            if (!root->left) {
                root->left = createNode(value);
            }
            // Kemudian right child jika kosong
            else if (!root->right) {
                root->right = createNode(value);
            }
            // Namun jika keduanya terisi, lanjut ke child nodes
            else {
                // Pilih subtree yang lebih pendek
                if (getHeight(root->left) <= getHeight(root->right)) {
                    root->left = insert(root->left, value, level + 1);
                } else {
                    root->right = insert(root->right, value, level + 1);
                }
            }
        }

        // Namun jika level saat ini penuh, lanjut ke level berikutnya
        else {
            if (getHeight(root->left) <= getHeight(root->right)) {
                root->left = insert(root->left, value, level + 1);
            } else {
                root->right = insert(root->right, value, level + 1);
            }
        }
    }
    // Jika sudah di level baru
    else {
        if (!root->left) {
            root->left = createNode(value);
        } else {
            root->right = insert(root->right, value, level + 1);
        }
    }
    
    return root;
}


// Menghapus nilai maksimum (root)
Node* deleteMax(Node* root) {
    if (!root) return NULL;
    if (!root->left && !root->right) {
        delete root;
        return NULL;
    }
    
    // Cari node terakhir
    Node* queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    Node* lastNode = NULL;
    Node* parentOfLast = NULL;
    
    while (front < rear) {
        Node* temp = queue[front++];
        
        if (temp->left) {
            queue[rear++] = temp->left;
            lastNode = temp->left;
            parentOfLast = temp;
        }
        if (temp->right) {
            queue[rear++] = temp->right;
            lastNode = temp->right;
            parentOfLast = temp;
        }
    }
    
    // Ganti nilai root dengan nilai node terakhir
    root->data = lastNode->data;
    
    // Hapus node terakhir
    if (parentOfLast->right == lastNode)
        parentOfLast->right = NULL;
    else
        parentOfLast->left = NULL;
        
    delete lastNode;
    
    // Heapify dari root
    heapify(root);
    
    return root;
}

// Print heap dengan inorder traversal
void printHeap(Node* root) {
    if (!root) return;
    
    printHeap(root->left);
    cout << root->data << " ";
    printHeap(root->right);
}

// Bersihkan memori
void cleanup(Node* root) {
    if (!root) return;
    
    cleanup(root->left);
    cleanup(root->right);
    delete root;
}

int main() {
    Node* root = NULL;
    
    // Insert beberapa nilai
    root = insert(root, 4);
    root = insert(root, 2);
    root = insert(root, 3);
    root = insert(root, 7);
    root = insert(root, 9);
    root = insert(root, 8);
    
    cout << "Heap setelah insert: ";
    printHeap(root);
    cout << endl;

    // Hapus nilai maksimum
    root = deleteMax(root);
    cout << "Heap setelah delete max: ";
    printHeap(root);
    cout << endl;
    
    // Bersihkan memori
    cleanup(root);
    
    return 0;
}