// Jonathan Frech, 22nd of July, 10th, 11th of August 2018

// A heap is a binary tree represented by a flat array.
// The d-th tree depth is represented by consecutive array segments
// of length 1<<d. A heap may not be fully filled, all holes need to be
// at the tree's bottom right.
// Finally, a heap's smallest element is at its top and both child nodes
// are heaps themselves.
// Heapsorts both generates a heap from the given array and uses the heap
// property to iteratively find the smallest element, efficiently regenerating
// the heap property as needed.
// Heapsort performs O(n ln n) in a worst-case scenario. It does not require
// any additional memory as it operates on the given array by in-place element
// manipulation and can be either iteratively or primitive-recursively implemented.
// The implementation shown here uses tail recursion which can be easily optimized
// by an apt compiler.

// include standard libraries
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

// heap orientation (dictates the sorted list's orientation)
#define CMP >

// trickle down an integer element at index idx under the assumption
// that both child nodes satisfy the heap property
void heapify(int *arr, int len, int idx) {
    int val = arr[idx], lft_idx = 2*idx+1, rgt_idx = 2*idx+2;
    
    // a leaf node satisfies the heap property
    if (lft_idx >= len) return;
    
    // if the right child node does not exist, the node
    // has to be on the second-last level
    int lft = arr[lft_idx];
    if (rgt_idx >= len) {
        if (lft CMP val)
            arr[lft_idx] = val, arr[idx] = lft;
        
        return;
    }
    
    // find CMPer child node
    int rgt = arr[rgt_idx], fnd, fnd_idx;
    if (lft CMP rgt) fnd = lft, fnd_idx = lft_idx;
    else             fnd = rgt, fnd_idx = rgt_idx;
    
    // trickle if necessary
    if (fnd CMP val) {
        arr[fnd_idx] = val, arr[idx] = fnd;
        heapify(arr, len, fnd_idx);
    }
}

// coerce an integer array into being a heap (heapify from the bottom up)
void build_heap(int *arr, int len) {
    for (int j = len/2-1; j >= 0; j--)
        heapify(arr, len, j);
}

// sort an integer array in decending order using heapsort
void heapsort(int *arr, int len) {
    build_heap(arr, len);
    
    while (len) {
        // swap smallest element with the currently viewed array's back
        int tmp = *arr; *arr = arr[len-1]; arr[len-1] = tmp;
        
        // rebuild the heap structure
        heapify(arr, --len, 0);
    }
}

// reverse an integer array
void reverse_array(int *arr, int len) {
    for (int j = 0, tmp; j < len/2; j++)
        tmp = arr[j], arr[j] = arr[len-j-1], arr[len-j-1] = tmp;
}

// generate a pseudo-randomly initialized integer array
int *random_array(int len) {
    int *arr = malloc(len * sizeof *arr);
    
    for (int j = 0; j < len; j++)
        arr[j] = rand() % 101 - 50;
    
    return arr;
}

// copy an integer array
int *copy_array(int *arr, int len) {
    int *new_arr = malloc(len * sizeof *arr);
    
    for (int j = 0; j < len; j++)
        new_arr[j] = arr[j];
    
    return new_arr;
}

// print an integer array
void print_array(int* arr, int len) {
    printf("{");
    for (int j = 0; j < len; j++)
        printf("%d%s", arr[j], j<len-1?", ":"");
    printf("}\n");
}

// test whether given integer array is sorted in CMP ord
bool is_sorted(int *arr, int len) {
    for (int j = 0; j < len-1; j++)
        if (arr[j] CMP arr[j+1])
            return false;
    
    return true;
}

// automatic testing
void test_heapsort() {
    for (int len = 0; len < 1000; len++)
        for (int run = 0; run < 10; run++) {
            int *arr = random_array(len), *org_arr = copy_array(arr, len);
            heapsort(arr, len);
            if (!is_sorted(arr, len)) {
                printf("[ERR] Automatic testing failed at length %d, run %d.\n", len, run);
                printf("      Original: "); print_array(org_arr, len);
                printf("      Sorted  : "); print_array(arr, len);
            }
            free(arr); free(org_arr);
        }
}

// test the heapsort algorithm's speed using lists of various lengths
void test_heapsort_performance(int N) {
    printf("(");
    for (int n = 0; n <= N; n++) {
        int len = (6300000)/N*n, *arr = random_array(len);
        
        clock_t beg = clock();
        heapsort(arr, len);
        clock_t end = clock();
        
        free(arr);
        double tim = (double) (end-beg) / CLOCKS_PER_SEC;
        printf("(%d, %f), ", len, tim);
        fflush(stdout);
    }
    printf(")\n");
    fflush(stdout);
}

int main() {
    //test_heapsort_performance(63);
    test_heapsort();
}