priorqueue.h

001   #ifndef __PRIORQUEUE_H
002   #define __PRIORQUEUE_H
003   
004   
005   // Estrutura-base da implementação:
006   // os campos são ponteiros para rotinas que abstraem
007   // todas as operações necessárias para gerenciar o heap
008   // e manter uma fila de prioridades
009   typedef struct {
010       // Compara as chaves de dois nós e retorna:
011       // * -1 se o primeiro elemento for menor do que o segundo;
012       // * 0 se o primeiro elemento for igual ao segundo;
013       // * 1 se o primeiro elemento for maior do que o segundo.
014       int (* Compare)(void *pq, int nIndex1, int nIndex2);
015   
016       // Compara a chave de um nó com uma chave fornecida,
017       // retornando um valor com a mesma convenção para Compare
018       int (* CompareKey)(void *pq, int nIndex, int nKey);
019   
020       // Retorna um valor inteiro associado ao nó
021       int (* GetId)(void *pq, int nIndex);
022   
023       // Sinaliza que um nó teve sua posição alterada
024       // no vetor que representa a árvore heap
025       void (* QueueIndexChanged)(void *pq, int nIndex);
026   
027       // Estabelece um novo valor para a chave de um nó
028       void (* SetKey)(void *pq, int nIndex, int nKey);
029   
030       // Intercambia a posição de dois nós no vetor
031       // que representa o heap
032       void (* Swap)(void *pq, int nIndex1, int nIndex2);
033   
034       // Armazena o número de elementos no heap
035       int nElems;
036   } TPriorityQueueControl;
037   
038   
039   void PriorQueueMinHeapify(void *pq, TPriorityQueueControl *pqc, int nIndex);
040   void PriorQueueBuildMinHeap(void *pq, TPriorityQueueControl *pqc);
041   int PriorQueueExtractMin(void *pq, TPriorityQueueControl *pqc);
042   void PriorQueueDecreaseKey(void *pq, TPriorityQueueControl *pqc, int nIndex,
043       int nNovaDist);
044   
045   
046   #endif  // __PRIORQUEUE_H