priorqueue.c

001   #include "priorqueue.h"
002   #include <stdlib.h>
003   
004   
005   // Dado o índice de um nó cujos filhos são raízes de heaps mínimos,
006   // este procedimento assegura a regra de heap mínimo para este nó,
007   // possivelmente gerando recursão para um de seus filhos
008   void PriorQueueMinHeapify(void *pq, TPriorityQueueControl *pqc, int nIndex)
009   {
010       int nLeft = (nIndex + 1) * 2 - 1, nRight = (nIndex + 1) * 2, nMaior;
011   
012       // Busca o índice do nó que contém a menor chave
013       if ((nLeft < pqc->nElems) && (pqc->Compare(pq, nLeft, nIndex) < 0)) {
014           nMaior = nLeft;
015       } else {
016           nMaior = nIndex;
017       }
018       if ((nRight < pqc->nElems) && (pqc->Compare(pq, nRight, nMaior) < 0)) {
019           nMaior = nRight;
020       }
021   
022       // Se for descoberta uma violação da regra do heap mínimo...
023       if (nMaior != nIndex) {
024           // ...intercambia os dois nós...
025           pqc->Swap(pq, nIndex, nMaior);
026           pqc->QueueIndexChanged(pq, nIndex);
027           pqc->QueueIndexChanged(pq, nMaior);
028   
029           // ...e gera recursão para o filho intercambiado
030           PriorQueueMinHeapify(pq, pqc, nMaior);
031       }
032   }
033   
034   
035   // Dado um vetor desordenado, este procedimento rearranja os elementos
036   // para que o vetor passe a representar um heap mínimo
037   void PriorQueueBuildMinHeap(void *pq, TPriorityQueueControl *pqc)
038   {
039       int i;
040   
041       // Assegura que todas as sub-árvores do heap
042       // respeitam a regra da relação entre pai e filho
043       for(i = (pqc->nElems >> 1) - 1; i >= 0; i--) {
044           PriorQueueMinHeapify(pq, pqc, i);
045       }
046   }
047   
048   
049   // Extrai o menor elemento de um heap e reorganiza-o
050   int PriorQueueExtractMin(void *pq, TPriorityQueueControl *pqc)
051   {
052       int nResult;
053   
054       if (pqc->nElems < 1) return -1;
055   
056       // Armazena a identificação do nó a ser retirado
057       nResult = pqc->GetId(pq, 0);
058   
059       // Diminui o tamanho do vetor que representa o heap
060       pqc->nElems--;
061   
062       // Intercambia o primeiro e o último nós
063       pqc->Swap(pq, 0, pqc->nElems);
064       pqc->QueueIndexChanged(pq, 0);
065   
066       // Assegura o respeito à regra do heap mínimo
067       PriorQueueMinHeapify(pq, pqc, 0);
068   
069       return nResult;
070   }
071   
072   
073   // Decrementa a chave associada a um nó do heap mínimo, possivelmente
074   // rearranjando os elementos para que a regra de relação entre pais e filhos
075   // seja respeitada
076   void PriorQueueDecreaseKey(void *pq, TPriorityQueueControl *pqc, int nIndex,
077       int nNovaDist)
078   {
079       int nParent;
080   
081       // Só prossegue se a operação for de decremento da chave
082       if (pqc->CompareKey(pq, nIndex, nNovaDist) <= 0) return;
083   
084       // Armazena o novo valor da chave
085       pqc->SetKey(pq, nIndex, nNovaDist);
086   
087       // Intercambia o nó com seu sucessor até respeitar a regra
088       // do heap mínimo
089       while (nIndex > 0) {
090           nParent = (nIndex - 1) >> 1;
091           if (pqc->Compare(pq, nParent, nIndex) <= 0) break;
092   
093           pqc->Swap(pq, nParent, nIndex);
094           pqc->QueueIndexChanged(pq, nParent);
095           pqc->QueueIndexChanged(pq, nIndex);
096   
097           nIndex = nParent;
098       }
099   }