#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define RIGHT_CHILD(i)  (((i) * 2) + 2)
#define PARENT(i)       (((i) - 1) / 2)
#define INIT_SIZE 2
#define GROW_SIZE	32
typedef int (*prioq_compare_t)(struct prioq_head *a, struct prioq_head *b);

struct prioq_head{
	    unsigned int index;
};		

struct user_data{
        struct prioq_head head;
		int data;
};		

struct prioq{
        struct prioq_head **heap;
	    size_t size;
        size_t used;
        prioq_compare_t compare;
};	


/*Создание очереди */
struct prioq *
prioq_new(prioq_compare_t compare)
{
	struct prioq *queue;

	queue = (struct prioq*)malloc(sizeof(struct prioq));

	if (queue == NULL) {
		fprintf(stderr, "prioq_new: can't allocate queue\n");
		return NULL;
	}

	memset(queue, 0, sizeof(*queue));

	queue->heap = (struct prioq_head**)malloc(sizeof(struct prioq_head *) * INIT_SIZE);

	if (queue->heap == NULL) {
		fprintf(stderr, "prioq_new: can't allocate heap\n");
		free(queue);
		return NULL;
	}

	memset(queue->heap, 0, sizeof(struct prioq_head *) * INIT_SIZE);

	queue->size = INIT_SIZE;
	queue->used = 0;
	queue->compare = ((compare != NULL) ? compare : compare);

	return queue;
}

#define NEW_SIZE(q)	(((q)->size + GROW_SIZE) * sizeof(struct prioq_head *))
#define OLD_SIZE(q)	((q)->size * sizeof(struct prioq_head *))

int prioq_put(struct prioq *queue, struct prioq_head *hp){

    int i;
	struct prioq_head** tmp;

	if (queue == NULL || hp == NULL) {
		fprintf(stderr, "prioq_put: NULL args\n");
		return NULL; 
    }
	if (queue->size == queue->used) {
		tmp = (struct prioq_head**)realloc(queue->heap, NEW_SIZE(queue));
		if (!tmp) {
			fprintf(stderr, "prioq_put: can't realloc heap\n");
			return -1;
		}
		memset(queue->heap + OLD_SIZE(queue), 0,
		       NEW_SIZE(queue) - OLD_SIZE(queue));
		queue->size += GROW_SIZE;
		queue->heap = tmp;
	}

	i = queue->used++;

	while (i && queue->compare(queue->heap[PARENT(i)], hp) < 0) {
 		queue->heap[i] = queue->heap[PARENT(i)];
		queue->heap[i]->index = i;
		i = PARENT(i);
	}

	queue->heap[i] = hp;
	hp->index = i;
    
	return 0;

}	

/*Функция сравнения*/
int
compare(struct prioq_head *a, struct prioq_head *b)
{
	struct user_data *ap = (struct user_data *) a;
	struct user_data *bp = (struct user_data *) b;

	if (ap->data > bp->data)
		return 1;
	else if (ap->data < bp->data)
		return -1;
	return 0;
}

/*---------------------------------------------*/
#define LEFT_CHILD(i)   (((i) * 2) + 1) 
int
prioq_heapify(struct prioq *queue)
{
    unsigned int index, largest;	
	
	struct prioq_head* tmp;
	
	for (index = 0,largest = LEFT_CHILD(index);
	    largest < queue->used;
        index = largest, largest = LEFT_CHILD(index)) {
		
        if (queue->compare(queue->heap[largest],
			queue->heap[largest+1]) < 0) {
            
			largest++;			
        }
	    if (queue->
			compare(queue->heap[index],
			queue->heap[largest])<0) {
			
			tmp = queue->heap[largest];
			queue->heap[largest] = queue->heap[index];
			queue->heap[largest]->index = index;
			queue->heap[index] = tmp;
			queue->heap[index]->index = largest;
		}
		else return 0;
	}	
	if ((largest == queue->used) 
		&& (queue->compare(queue->heap[index],
		    queue->heap[largest]) < 0)) {
        
		tmp = queue->heap[largest];
		queue->heap[largest] = queue->heap[index];
		queue->heap[largest]->index = index;
		queue->heap[index] = tmp;
		queue->heap[index]->index = largest;
	}
	
	return 1;	
}


/*------------------------------------------------*/
void 
prioq_remove(struct prioq *queue, struct prioq_head *hp) 
{
    
	if (hp->index > queue->used)
        fprintf(stderr,"prioq_remove: index out of range\n");
	
	int index = hp->index;
	
	while (index > 0){
	    queue->heap[index] = queue->heap[PARENT(index)];
		queue->heap[index]->index = PARENT(index); 
        index = PARENT(index);
	}
	
	queue->used--;
	
	int used = queue->used;
	queue->heap[0] = queue->heap[used];
    queue->heap[0]->index = used;
	prioq_heapify(queue);
}	

void
prioq_free(struct prioq* queue)
{
        
	if (queue == NULL) {
        fprintf(stderr,	"prioq_free:The queue not exists\n");
		// тут я хотел написать return NULL,
		// но компилятор против. А может и не 
		// обязательно  return NULL  тут писать?;
	}	
	else {
	   
	    free(queue);
		fprintf(stderr,"prioq_free: the queue is free\n");	
	}
	
}	

	
int main(void){
    struct prioq *q=prioq_new(compare); 
    struct user_data a,b;
	struct prioq_head *p,*s;
	struct user_data* dat;
		
    a.data = 0;
    b.data = 5;
	p = &a.head;
	s = &b.head;
	
	
	
	prioq_put(q,p);
	prioq_put(q,s);
	prioq_free(q);	
	//prioq_remove(q,p);
	//dat = (struct user_data*)q->heap[0];
	return 1;	
}