// ------------------------------------------------------------------------------------------------
// ---- Secao 6.5 do Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein) -----------------------
// ---- Implementacao de Heaps Minimos (fila de prioridades) --------------------------------------
// ------------------------------------------------------------------------------------------------
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <ctime>
using namespace std;

typedef struct heap {
    int* vet;//vetor do heap de indices
    int* pos;//posicao dos indices no vetor vet
    double* chave;// valor dos indices
    int N;// numero de elementos no heap
    int tam;// tamanho maximo do heap
} heap;

void heap_create(heap* H, double* chave, int tam);
int heap_extract_min(heap* H);
bool heap_vazio(heap* H);
void heap_decrease_key(heap* H, int indice, double chave);
void heap_delete(heap* H);


int main() {
	FILE* arq = fopen("saida_heap.txt","w");
    int N=10000;
    double* vetor = new double [N];
    srand (time(NULL));
    for (int i=0;i<N;i++) {
        vetor[i] = (double) rand()/RAND_MAX;
        fprintf(arq,"%f ",vetor[i]);
    }
    fprintf(arq,"\n\n");

    // Ordenação de um vetor usando HEAP MINIMO
    heap H;
    heap_create(&H,vetor,N);
    //while (!heap_vazio(&H)) {
    for (int i=0; i<N; i++) {
        int j = heap_extract_min(&H);
        fprintf(arq,"%f ",vetor[j]);
    }
	fclose(arq);
    heap_delete(&H);
    delete [] vetor;
    return 0;
}

// ------------------------------------------------------------------------------------------------
// ---- Algoritmos de HEAP ------------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------
void trocar(int& x, int& y) {int z = x; x = y; y = z;}

void heapify(heap* H, int i) {
    int m = i;
    int esq = 2*i+1;
    int dir = esq+1;
    if ((esq<H->N)&&(H->chave[H->vet[esq]]<H->chave[H->vet[m]])) m = esq;
    if ((dir<H->N)&&(H->chave[H->vet[dir]]<H->chave[H->vet[m]])) m = dir;
    if (m != i) {
        H->pos[H->vet[i]] = m;
        H->pos[H->vet[m]] = i;
        trocar(H->vet[i], H->vet[m]);
        heapify(H,m);
    }
}

void heap_build(heap* H) {
    int i, N=H->N;
    for (i=N/2-1; i>=0; i--) {
        heapify(H,i);
    }
    //imprimir_vetor(H->vet,H->N,"saida_heap_build.txt");
}

void heap_create(heap* H, double* chave, int tam) {
    H->N = tam;
    H->tam = tam;
    H->chave = chave;
    H->vet = new int [tam];
    H->pos = new int [tam];
    for (int i=0; i<tam; i++) {
        H->vet[i] = i;
        H->pos[i] = i;
    }
    heap_build(H);
}

void heap_decrease_key(heap* H, int indice, double chave) {
    H->chave[indice] = chave;
    int i = H->pos[indice];
    int pai = (i-1)/2;
    while ((i>0)&&(H->chave[H->vet[pai]]>chave)) {
        H->pos[H->vet[i]] = pai;
        H->pos[H->vet[pai]] = i;
        trocar(H->vet[pai], H->vet[i]);
        i = pai;
    }
}

// Retorna o indice com menor valor chave
int heap_extract_min(heap* H) {
    if (heap_vazio(H)) return -1;
    int N = --H->N;
    int min = H->vet[0];
    H->pos[H->vet[N]] = 0;
    H->vet[0] = H->vet[N];
    heapify(H,0);
    return min;
}

bool heap_vazio(heap* H) {
    if (H->N <= 0) return true;
    return false;
}

void heap_delete(heap* H) {
    if (H->vet!=NULL) free(H->vet);
    if (H->pos!=NULL) free(H->pos);
    H->chave = NULL;
    H->vet = NULL;
    H->pos = NULL;
    H->N = 0;
    H->tam = 0;
}