HW2_merge_sort

#include <cstdio>
#include <cstdlib>
#define _CRT_SECURE_NO_WARNINGS

void swap(int i, int j, int * heap)
{
    int t = 0;
    t = heap[i];
    heap[i] = heap[j];
    heap[j] = t;
    return;
}

void sift_up(int n, int *heap)
{
    int i = n;
    while (i > 0)
    {
        if (heap[i] <= heap[(i - 1) / 2])
            return;
        swap(i, (i - 1) / 2, heap);
        i = (i - 1) / 2;
    }
    return;
}

void sift_down(int n, int *heap)
{
    int i = 0;
    while (i < n - 1)
    {
        if (heap[i] >= heap[2 * i + 2] && heap[i] >= heap[2 * i + 1])
            return;
        else if (heap[i] < heap[2 * i + 2] && heap[2 * i + 2]>heap[2 * i + 1])
        {
            swap(2 * i + 2, i, heap);
            i = 2 * i + 2;
        }
        else
        {
            swap(2 * i + 1, i, heap);
            i = 2 * i + 1;
        }
    }
}

int * create_heap(int n, int * arr)
{

    int * heap = (int *)malloc(n * sizeof(int));
    heap[0] = arr[0];
    for (int i = 1; i < n; i++)
    {
        heap[i] = arr[i];
        sift_up(i, heap);
    }
    return heap;
}

int del_max(int n, int * heap)
{
    swap(0, n - 1, heap);
    int t = heap[n - 1];
    heap[n - 1] = 0;
    n--;
    sift_down(n, heap);
    return t;
}

int main()
{
    int n = 0, t = 0;
    scanf("%d", &n);
    int * arr = (int*)malloc(n*sizeof(int));
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
    int *heap = create_heap(n, arr);
    for (int i = 0; i < n; i++)
        printf("%d ", heap[i]);
    printf("\n");
    printf("%d\n", del_max(n, heap));
    for (int i = 0; i < n; i++)
        printf("%d ", heap[i]);
    return 0;
}