terça-feira, 14 de abril de 2015

Programação em C - Heap Sort

Olá pessoal, nesse post irei disponibilizar o código de uma implementação do algoritmo de ordenação Heap Sort na linguagem C.

Anteriormente havia postado as implementações do Insertion Sort, Bubble Sort e Selection Sort. Essas implementações são bem simples e não oferecem dificuldades. O heap sort tem complexidade nlogn no pior caso, ou seja, é melhor do que os algoritmos falados anteriormente no pior caso.

A implementação do Heap Sort também é simples, mas você terá que entender alguns conceitos a mais para implementá-lo.

Uma heap obedece às propriedades:

c[i] >= c[2i]
c[i] >= c[2i + 1]

Essa definição pode ser facilmente visualizada através de uma árvore.

Os nós são numerados de 1 a n. O nó 1 não tem pai e é chamado de raiz. O nó (i/2) é pai do nó i para 1 < i <= n.

Os nós 2i e (2i + 1) são os filhos à esquerda e à direita respectivamente do nó i para 1 <= i <= n/2.

Um nó i só tem filho esquerdo se 1 <= i <= n/2. Um nó i só tem filho direito se 2i + 1 <= n.

Um nó i é uma folha se não tem filhos, ou seja, 2i > n.

Todo nó i é raiz da subárvore formada pelos nós i, 2i, 2i + 1, 4i + 1, 4i + 2, ...

Numa heap, a chave em cada nó é maior do que as chaves em seus filhos. A chave no nó raiz é a maior chave do conjunto. A maior chave sempre está na posição 1 do vetor (indexando a partir do 1).

É preciso implementar alguns métodos tais como o método refaz (rebuild) para reconstruir a heap, o método construir (build) para construir a heap e o método heap sort que irá utilizar esses métodos.

Simples não é mesmo? Para entender melhor assista a esse vídeo:



 Veja o código da implementação do heap sort em C:



Nenhum comentário: