//  Heap_sort_Decreasing_order_Using_MinHeap

#include <iostream>

using namespace std;

void heapSort(int a[], int n, int h);
void buildMinHeap(int a[], int n, int h);
void minHeapify(int a[], int h, int i);
int left(int i);
int right(int i);

int main(){
    int a[20], n, h;
    cout << "How many numbers?: ";
    cin >> n;
    h = n;
    cout << "\nEnter numbers: ";
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    heapSort(a, n, h);
    cout << "\nOutput numbers in sorted order: ";
    for(int i = 1; i <= n; ++i)
        cout << " " << a[i];
    return 0;
}

void heapSort(int a[], int n, int h){
    buildMinHeap(a, n, h);
    for(int i = n; i >= 2; --i){
        swap(a[1], a[i]);
        h--;
        minHeapify(a, h, 1);
    }
}

void buildMinHeap(int a[], int n, int h){
    h = n;
    for(int i = (n/2); i >= 1; --i)
        minHeapify(a, h, i);
}

void minHeapify(int a[], int h, int i){
    int l = left(i);
    int r = right(i);
    int smallest;
    if(l <= h && a[l] < a[i])
        smallest = l;
    else
        smallest = i;
    if(r <= h && a[r] < a[smallest])
        smallest = r;
    if(smallest != i){
        swap(a[i], a[smallest]);
        minHeapify(a, h, smallest);
    }
}

int left(int i){
    return (2 * i);
}

int right(int i){
    return (2 * i + 1);
}

                //  heap_decrease_key

#include <iostream>

using namespace std;

void HeapDecreaseKey(int a[], int n, int h);
void BuildMinHeap(int a[], int n, int h);
void MinHeapify(int a[], int h, int i);
int left(int i);
int right(int i);



int main(){
    int a[100], n, h;
    cout << "How many items?: ";
    cin >> n;
    h = n;
    cout << "\nEnter the values: ";
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    HeapDecreaseKey(a, n, h);
    cout << "\nResulting min-heap: ";
    for(int j = 1; j <= n; ++j)
        cout << " " << a[j];
return 0;
}

void HeapDecreaseKey(int a[], int n, int h){
    int key, i;
    BuildMinHeap(a, n, h);
    cout << "\nKey value: ";
    cin >> key;
    cout << "\nIndex: ";
    cin >> i;
    if(key > a[i])
        cout << "\nNew key is greater than current key";
    a[i] = key;
    while(i>1 && a[i/2]>a[i]){
        swap(a[i], a[i/2]);
        i = i/2;
    }
}

void BuildMinHeap(int a[], int n, int h){
    h = n;
    for(int i = (n/2); i >= 1; --i)
        MinHeapify(a, h, i);
}

void MinHeapify(int a[], int h, int i){
    int l = left(i);
    int r = right(i);
    int smallest;
    if(l <= h && a[l] < a[i])
        smallest = l;
    else
        smallest = i;
    if(r <= h && a[r] < a[smallest])
        smallest = r;
    if(smallest != i){
        swap(a[i], a[smallest]);
        MinHeapify(a, h, smallest);
    }
}

int left(int i){
    return (2*i);
}

int right(int i){
    return (2*i + 1);
}

                //  min_heap_insert

#include <iostream>

using namespace std;

void MinHeapInsert(int a[], int n, int h);
void HeapDecreaseKey(int a[], int n, int h);
void BuildMinHeap(int a[], int n, int h);
void MinHeapify(int a[], int h, int i);
int left(int i);
int right(int i);



int main(){
    int a[100], n, h;
    cout << "How many items?: ";
    cin >> n;
    h = n;
    cout << "\nEnter the values: ";
    for(int i = 1; i <= n; ++i)
        cin >> a[i];

    MinHeapInsert(a,n,h);
    cout << "\nResulting min-heap: ";
    for(int j = 1; j <= (n+1); ++j)
        cout << " " << a[j];
return 0;
}

void MinHeapInsert(int a[], int n, int h){
    h++;
    a[h] = 99999;
    HeapDecreaseKey(a, n, h);
}

void HeapDecreaseKey(int a[], int n, int h){
    int key, i;
    BuildMinHeap(a, n, h);
    cout << "\nKey value: ";
    cin >> key;
//    cout << "\nIndex: ";
//    cin >> i;
    if(key > a[h])
        cout << "\nNew key is greater than current key";
    a[h] = key;
    while(h>1 && a[h/2]>a[h]){
        swap(a[h], a[h/2]);
        h = h/2;
    }
}

void BuildMinHeap(int a[], int n, int h){
    h = n;
    for(int i = (n/2); i >= 1; --i)
        MinHeapify(a, h, i);
}

void MinHeapify(int a[], int h, int i){
    int l = left(i);
    int r = right(i);
    int smallest;
    if(l <= h && a[l] < a[i])
        smallest = l;
    else
        smallest = i;
    if(r <= h && a[r] < a[smallest])
        smallest = r;
    if(smallest != i){
        swap(a[i], a[smallest]);
        MinHeapify(a, h, smallest);
    }
}

int left(int i){
    return (2*i);
}

int right(int i){
    return (2*i + 1);
}

                    //  heap_extract_min

#include <iostream>

using namespace std;

void BuildMinHeap(int a[], int n, int h);
void MinHeapify(int a[], int h, int i);
int left(int i);
int right(int i);
int HeapExtractMin(int a[], int n, int h);

int main(){
    int a[100], n, h;
    cout << "How many items ?: ";
    cin >> n;
    h = n;
    cout << "\nEnter the items: ";
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    int m = HeapExtractMin(a, n, h);
    cout << "\nThe Minimum is: " << m;
return 0;
}

int HeapExtractMin(int a[], int n, int h){
    BuildMinHeap(a, n, h);
    int min;
    if(h < 1)
        cout << "\nERROR: Heap Underflow";
    min = a[1];
    a[1] = a[h];
    h--;
    MinHeapify(a, h, 1);
    return min;
}

void BuildMinHeap(int a[], int n, int h){
    h = n;
    for(int i = (n/2); i >= 1; --i)
        MinHeapify(a, h, i);
}

void MinHeapify(int a[], int h, int i){
    int l = left(i);
    int r = right(i);
    int smallest;
    if(l <= h && a[l] < a[i])
        smallest = l;
    else
        smallest = i;
    if(r <= h && a[r] < a[smallest])
        smallest = r;
    if(smallest != i){
        swap(a[i], a[smallest]);
        MinHeapify(a, h, smallest);
    }
}

int left(int i){
    return (2*i);
}

int right(int i){
    return (2*i + 1);
}