23-Priority Queue with increase_key implement

[Pin-Jiun]

#include <iostream>
#include <algorithm>

using namespace std;
typedef struct arr
{
    int heap_size = 6;
    int array_size = 6;
    int arr[7] = {-1, 1, 3, 4, 5, 7, 8};
} Arr;
int parent(int);
int left_child(int);
int right_child(int);
void build_max_heap(Arr &A);
void max_heapify(Arr &, int);
int heap_maximum(Arr &);
int extract_maximum(Arr &);
void heap_increase_key(Arr &, int, int);
void max_heap_insert(Arr &, int);
void show_heap(Arr &);
int main(void)
{
    Arr A;
    build_max_heap(A);
    show_heap(A);
    cout << "heap_maximum(A) = " << heap_maximum(A) << '\n';
    cout << "extract_maximum(A) = " << extract_maximum(A) << '\n';
    cout << "extract_maximum(A) = " << extract_maximum(A) << '\n';
    max_heap_insert(A, 12);
    show_heap(A);
    heap_increase_key(A, 2, 15);
    show_heap(A);
}
int parent(int i)
{
    if (i == 0)
    {
        return 0;
    }
    return i / 2;
}

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

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

void build_max_heap(Arr &A)
{
    A.heap_size = A.array_size;
    for (int i = A.array_size / 2; i >= 1; i--)
    {
        max_heapify(A, i);
    }
}

void max_heapify(Arr &A, int i)
{
    int l = left_child(i);
    int r = right_child(i);
    int largest = 0;
    if ((l <= A.heap_size) && (A.arr[l] > A.arr[i]))
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if ((r <= A.heap_size) && (A.arr[r] > A.arr[largest]))
    {
        largest = r;
    }
    if (largest != i)
    {
        swap(A.arr[i], A.arr[largest]);
        max_heapify(A, largest);
    }
}

int heap_maximum(Arr &A)
{
    return A.arr[1];
}

int extract_maximum(Arr &A)
{
    if (A.heap_size < 1)
    {
        cout << "heap underflow" << '\n';
        return -1;
    }
    int max = A.arr[1];
    A.arr[1] = A.arr[A.heap_size];
    A.heap_size = A.heap_size - 1;
    max_heapify(A, 1);
    return max;
}

void heap_increase_key(Arr &A, int i, int key)
{
    if (key < A.arr[i])
    {
        cout << "new key is smaller than current key" << '\n';
        return;
    }
    A.arr[i] = key;
    while (i > 1 && A.arr[parent(i)] < A.arr[i])
    {
        swap(A.arr[i], A.arr[parent(i)]);
        i = parent(i);
    }
}

void max_heap_insert(Arr &A, int key)
{
    A.heap_size = A.heap_size + 1;
    A.arr[A.heap_size] = -99999;
    heap_increase_key(A, A.heap_size, key);
}

void show_heap(Arr &A)
{
    for (int i = 1; i <= A.heap_size; i++)
    {
        cout << A.arr[i] << ' ';
    }
    cout << '\n';
}

https://ithelp.ithome.com.tw/articles/10269601