HeapSort

main.c

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

#define ValType int

//V1 < V2
#define IS_LESS(v1, v2)  (v1 < v2)

void siftDown( ValType *a, int start, int count);

#define SWAP(r,s)  do{ValType t=r; r=s; s=t; } while(0)

void heapsort( ValType *a, int count)
{
    int start, end;

    /* heapify */


    // Processo de construção do heap começa pelo final
    // O maior valor será a raiz
    // No final do array ficam as folhas
    for (start = (count-2)/2; start >=0; start--) {
        siftDown( a, start, count);
    }

    for (end=count-1; end > 0; end--) {
    	
        SWAP(a[end],a[0]);
        // Conforme executa as trocas, o maior elemento fica no final, portanto não será mais acessado
        // executa uma nova checagem na arvore
        siftDown(a, 0, end);
    }
}

// Verifica um trecho da arvore, a raiz e 2 folhas
void siftDown( ValType *a, int start, int end)
{
    int root = start;

    while ( root*2+1 < end ) {
        int child = 2*root + 1;
        //Se o nó da direita for menor, incrementa pra comparar com o pai
        if ((child + 1 < end) && IS_LESS(a[child],a[child+1])) {
            child += 1;
        }

        //Se raiz menor que filho
        if (IS_LESS(a[root], a[child])) {
        	//Filho passa a ser raiz
            SWAP( a[child], a[root] );
            root = child;
        }
        else
            return;
    }
}


int main()
{
    int ix;
    int valsToSort[] = { 11, 5, 4, 3, 7, 8, 9, 10, 2, 1, 6, 12   };
#define VSIZE (sizeof(valsToSort)/sizeof(valsToSort[0]))

    heapsort(valsToSort, VSIZE);
    printf("{");
    for (ix=0; ix<VSIZE; ix++) printf(" %i ", valsToSort[ix]);
    printf("}\n");
    return 0;
}