#include <stdio.h>
#include <stdbool.h>

#define MAXSIZE 9

typedef struct {
    int r[MAXSIZE+1]; // first index used as tmp, not real data
    int len;
}SqList;

void swap(SqList *L, int i, int j) {
    int tmp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = tmp;
}


void heap_adjust(SqList *L, int s, int len) {
    int temp, i;

    temp = L->r[s]; // s(start) index may be a invalid element in this heap and try adjust

    for (i=s*2; i<=len; i*=2) { // compare with child
        if (i<len && L->r[i] < L->r[i+1]) {
            i++; // select the max child
        }

        if (temp >= L->r[i]) {
            break; // need not adjust
        }

        L->r[s] = L->r[i]; //need not swap, because always use temp compare with next level child

        s = i; // next loop, now s sub tree root node may be a invalid element
    }

    L->r[s] = temp; // finally, must be found the right place(or not changed)

}


void heap_adjust_2(SqList *L, int s, int len) {
    printf("use test function\n");
    int temp, i;

    temp = L->r[s]; // s(start) index may be a invalid element in this heap and try adjust

    for (i=s*2; i<=len; i*=2) { // compare with child
        if (i<len && L->r[i] < L->r[i+1]) {
            i++; // select the max child
        }

        if (temp >= L->r[i]) {
            break; // need not adjust
        }

        swap(L, s, i); //need not swap, because always use temp compare with next level child

        s = i; // next loop, now s sub tree root node may be a invalid element
    }

    L->r[s] = temp; // finally, must be found the right place(or not changed)

}

void heap_sort(SqList *L) {
    // init serial to a heap first(type: big top), down->up and right->left
    int i, j;
    for (i=L->len/2; i>0; --i) {
        heap_adjust(L, i, L->len);
        //heap_adjust_2(L, i, L->len);
    }


    for (j=L->len; j>1; --j) {
        swap(L, 1, j);
        heap_adjust(L, 1, j-1);
    }

}

int main(void) {
    SqList list = {
        {999,50,10,90,30,70,40,80,60,20},
        MAXSIZE
    };

    heap_sort(&list);
    printf("after heap_sort:\n");
    for (int i=0; i<=MAXSIZE; i++) {
        printf("index: %d, value: %d\n",i,list.r[i]);
    }
    return 0;
}