Filas prioritária( Algoritmos e estruturas de dados 1)

filas prioritárias
->estrutura de dados linear
->tipo de dados
    abstracto (ADT) com as seguintes prioridades:
* supostas operações de - inserção( de um novo elemento na fila)
                -remoção do elemento que esta na cabeça  da fila isto é, o elemento maior  prioridade,tipicamente o elemento com maior de chave

API da fila prioritária(PG-Priority Queue)

void insert QP(PQueu *pq,int elemento)
int DelMaxPQ(PQueu*pq)


exemplo: os seguintes n=8, a chegar por esta ordem á fila
5,2,7,3,1,8,6,4



3 Implementações de possíveis PQ:
a)Usar um vector não ordenado
    - quando chega um elemento é colocado no final do vector(custo 1-constante)
    - quando queremos remover o maior elemento temos fazer n comparações para determinar o maior elemento

b)Usar um vector ordenado
- quando chega um novo elemento é feita a fusão ordenada com o vector ordenado já  existente(inserção tem custo linear)
- remoção com custo, constante-1

c)Binary Heap
- implementar uma árvore binária balanceado usando um vector

ex: árvore binária
- estrutura de dados não linear em que casa elemento tem: 0,1, ou 2 filhos
-existe uma só raiz na árvore
-> A árvore binária satisfaz as seguintes condições
   - todos os niveis estão completamente preenchido excepto o ultimo nível que pode estar parcialmente preenchido

-> Para uma Binary Heap
que implemente uma fila prioritária(PQ) sem elementos repetidos, dado qualquer elemento da árvore binária ele tem que ser sempre maior que os seus filhos (0,1, ou 2 filhos)

->nuance de implementação vamos deixar a posição 0 do vector da raiz aparece na posição 1
-> Dado um elemento da posição(índice) k o seu pai esta na posição k/2(divisão inteiro)
->os filhos do elemento de índice k estão nas posições 2*k e 2*k+1