Heaps e Filas de Prioridade. Fundamentos 3 Filas de Prioridade Uma fila de prioridade é uma lista...

Heaps e Filas de Prioridade

Fundamentos

3

Filas de Prioridade

Uma fila de prioridade é uma lista de itens na qual cada item possui uma prioridade associada.

Pode-se determinar o item que tem a maior e o que tem a menor prioridade, por exemplo.

Itens são inseridos em filas de prioridade em qualquer ordem. A exclusão de itens é feita em ordem decrescente de prioridade.

4

Filas de Prioridade

Filas de prioridade são containers que possuem as seguintes operações: enqueue

colocar objetos no container; findMin (ou findMax)

retornar o objeto de menor prioridade no container dequeueMin ( ou dequeueMax)

remover o menor objeto do container.

Uma fila de prioridades é usada para armazenar um conjunto de chaves de um conjunto ordenado de chaves K.

5

Árvore Binária Perfeita

Definição (Árvore Binária Perfeita) 

Uma árvore binária perfeita de altura h 0, é uma árvore binária {R, TL, TR} com as seguintes propriedades.

1. Se h=0, TL = 0 e TR = 0.

2. Para h>0 tanto TL quanto TR são árvores

binárias perfeitas de altura h-1.

6

Árvore Binária Completa

Definição (Árvore Binária Completa)  Uma árvore binária completa de altura h 0, é uma árvore binária {R, TL, TR} com as seguintes propriedades.

1. Se h=0, TL = 0 e TR = 0.

2. Para h>0 existem duas possibilidades1. TL é uma árvore binária perfeita de altura h-1 e TR é uma

árvore binária completa de altura h-1; ou

2. TL é uma árvore binária completa de altura h-1 e TR é uma

árvore binária perfeita de altura h-2.

7

Exemplo de árvores perfeitas e completas

8

Árvore N-aria Completa

Definição (Árvore N-aria Completa)  Uma árvore N-aria completa de altura h 0, é uma árvore N-aria {R, T0, T1, T2, ... TN-1} com as seguintes propriedades.

1. Se h=0, T1 = para todo i, 0 i < N. 2. Para h>0 existe um j, 0 j < N tal que

1. Ti é uma árvore N-aria perfeita de altura h-1 para todo i: 0 i < j;

2. Tj é uma árvore N-aria completa de altura h-1;

3. Ti é uma árvore N-aria perfeita de altura h-2 para todo i:j<i<N.

9

Árvore N-aria completa

Uma árvore completa é uma árvore na qual todos os níveis estão cheios exceto o último e este nível é cheio da esquerda para a direita.

10

Heap

As implementações de filas de prioridade são baseadas em um tipo especial de árvore chamado de heapHá dois tipos de heap (min e max)Definição ((Min) Heap)  Um (Min) Heap   é uma árvore, {R, T0, T1, T2, ... TN-1} com as seguintes propriedades:

1. Cada sub árvore de T é um heap, 2. A raiz de T é menor ou igual do que a raiz de cada sub

árvore de T. Ou seja, R Ri para todo i, 0 i n , aonde Ri é a raiz de Ti.

11

Heap Binário

Um heap binário é uma árvore binária ordenada que tem a forma de árvore completa.

Um heap binário pode ser implementado sobre um “array”, o que dispensa o armazenamento de ponteiros para a montagem da árvore.

12

Incluir Itens em um Heap Binário Como o heap resultante da inclusão deve ser uma árvore completa só existe um local para a inclusão.Para incluir o item de chave 2 no heap da figura verifica-se a posição da inclusão (figura (a) ). A seguir reajusta-se o heap até chegar à posição adequada (figuras (b) e (c)). Finalmente faz-se a inclusão (figura (d)).

13

Remover Itens de um Heap Binário

O menor dos itens está sempre na raiz de um heap mínimo.

A última linha do heap deve ser esvaziada da direita para a esquerda na remoção de itens.

O dado a ser removido está na raiz mas o nó a ser removido está em folha.

14

Exemplo de HeapNo heap da figura a operação dequeueMin remove a chave 2 do heap mas o nó contendo 6 é que deve ser removido.O buraco deixado pela remoção da raiz deve ser reposicionado no heap, descendo até permitir a reinserção na árvore da chave 6 que ocupava a posição do heap a ser eliminadaPara afastar da raiz um buraco este troca de lugar com o menor de seus dois filhos.O processo continua até o buraco atingir uma folha da árvore ou uma posição adequada à chave que necessita ser reposicionada na árvore.

Implementação Java

16

Implementação

17

Interface PriorityQueue

// pgm11_01.txt

public interface PriorityQueue

extends Container

{

void enqueue (Comparable object);

Comparable findMin ();

Comparable dequeueMin ();

}

18

Interface MergeablePriorityQueue

// pgm11_02.txt

public interface MergeablePriorityQueue

extends PriorityQueue

{

void merge (MergeablePriorityQueue queue);

}

19

Campos de BinaryHeap

// pgm11_03.txt

public class BinaryHeap

extends AbstractContainer

implements PriorityQueue

{

protected Comparable[] array;

// ...

}

20

Métodos Construtor e purge da classe

BinaryHeap

// pgm11_04.txtpublic class BinaryHeap extends AbstractContainer implements PriorityQueue{ protected Comparable[] array;

public BinaryHeap (int length){ array = new Comparable[length + 1]; }

public void purge () {

while (count > 0) array [count--] = null;

} // ...}

21

Método enqueue da classe BinaryHeap

• Como o heap resultante da inclusão deve ser uma árvore completa só existe um local para a inclusão

• Este local (vazio ou buraco) vai “subir” no heap até encontrar seu ligar, deixando para baixo os valores menores do que o objeto o incluir no heap

• A “subida” no heap é feita buscando-se a posição do array obtida da divisão por dois da posição corrente

• Quando o buraco parar de “subir” nele inclui-se o objeto

22

Método enqueue da classe BinaryHeap

// pgm11_05.txt public void enqueue (Comparable object) {

if (count == array.length - 1) throw new ContainerFullException ();++count;int i = count;while (i > 1 && array [i/2].isGT (object)){ array [i] = array [i / 2]; i /= 2;}array [i] = object;

}

23

Método findMin da classe BinaryHeap

// pgm11_06.txtpublic class BinaryHeap extends AbstractContainer implements PriorityQueue{ protected Comparable[] array;

public Comparable findMin () {

if (count == 0) throw new ContainerEmptyException ();return array [1];

} // ...}

24

Método dequeue da classe BinaryHeap

O elemento a ser removido é o da raiz do heapO objeto que estava no último nó do heap deve procurar seu lugar no heap pois esse nó vai desaparecerInicia-se pela raiz, agora vazia, testando-se seus dois filhos para verificar o menorSe o objeto que estava no último nó for menor que os filhos da raiz termina a repetiçãoCaso contrário a raiz (objeto que estava no último nó) troca de lugar com o menor de seus dois filhos e passa a ser a raiz do heap corrente a pesquisarQuando a repetição termina a raiz no heap corrente recebe o objeto que estava no último nó

25

Método dequeue da classe BinaryHeap public Comparable dequeueMin () {

if (count == 0) throw new ContainerEmptyException ();Comparable result = array [1];Comparable last = array [count];--count;int i = 1;while (2 * i < count + 1){ int child = 2 * i; if (child + 1 < count + 1

&& array [child + 1].isLT (array [child]))child += 1;

if (last.isLE (array [child]))break;

array [i] = array [child]; i = child;}array [i] = last;return result;

}

Exemplos

27

Exemplos

Serão apresentados dois exemplos de uso de Filas de Prioridade

O primeiro exemplo é absolutamente trivial com inclusão e exclusão de objetos manualmente, via teclado

O segundo exemplo consiste em uma simulação de eventos discretos

28

Exemplo de uso de Fila de Prioridade em simples entrada e saída de dados

Exemplo usando o teclado para inserir dados inteiros em uma fila de prioridade

O usuário recebe um “prompt” para escolher entre inserir, remover dados, listas a fila de prioridade ou encerrar o programa

Caso escolha a inserção o usuário deve entrar com o dado

29

Composição do código

A hierarquia de classes já foi apresentada no estudo da classe BinaryHeap

Serão apresentadas as classes específicas desta aplicação Classe de Dados Classe da Aplicação Fila de Prioridade

30

Classe de Dados (1)import cap5.*;

import java.io.*;

public class DataAreaextends AbstractObjectimplements Serializable{ private String numero; private String transacao; final private int TAMANHO_INT = 2; public DataArea() { this.numero = ""; } public DataArea( String numero) { if ( numero.length() < TAMANHO_INT ) { numero = "0"+numero; } this.numero = numero; }

31

Classe de Dados (2)public DataArea( BufferedReader br )

throws IOException { int i = 0; String s, line = br.readLine(); if ( line == null ) { transacao = "err"; return; } transacao = line.substring(i,1);

i = 2;

if ( transacao.compareToIgnoreCase( "i" ) == 0 ){ numero = line.substring(i,i+TAMANHO_INT); i += TAMANHO_INT+1; nome = line.substring(i,i+TAMANHO_NOME); i += TAMANHO_NOME+2; s = line.substring(i,line.length()); salario = Double.parseDouble( s ); }

}

32

Classe de Dados (3) public String getNumero() { return numero; }

public String getTransacao() { return transacao; } public void setNumero( String numero ) { this.numero = numero; } } public void imprime() { System.out.println ("Numero = " + numero ); } protected int compareTo (cap5.Comparable object) {

DataArea arg = (DataArea) object;return numero.compareToIgnoreCase( arg.numero );

}}

33

FilaPrioridade01 (1)import cap5.*;import dados.*;

import java.io.*;import corejava.*;

public class FilaPrioridade01{ private static void lerDados( PriorityQueue listaP ) {

DataArea data = null;String transacao = "ok";

try { BufferedReader br = new BufferedReader( new FileReader("xxxx.zzz") );

while ( transacao.compareToIgnoreCase( "err" ) != 0 ){ data = new DataArea( br ); transacao = data.getTransacao(); if ( transacao.compareToIgnoreCase( "i" ) == 0 ) stack.push( data ); }br.close();}

catch(Exception e){}

}

34

FilaPrioridade01 (2)

public static void main (String[] args){ String numero; DataArea data; Enumeration todos;

PriorityQueue filaP = new LeftistHeap(); lerDados( listaP );

boolean continua = true; while (continua) { System.out.println('\n' + “==================");

System.out.println('\n' + "O que deseja fazer?");System.out.println('\n' + "1. Inserir");System.out.println("2. Remover");System.out.println("3. Listar");System.out.println("4. Sair");

35

FilaPrioridade01 (3)

int opcao = Console.readInt('\n' + "Digite um número entre 1 e 4:");switch (opcao) { case 1:

{ numero = Console.readLine('\n' + "Digite o numero: "); data = new DataArea (numero);

filaP.enqueue(data); System.out.println('\n' + "Inserido com sucesso!"); break; }case 2: // Remover { data = (DataArea) filaP.dequeue(); System.out.println('\n' + data.getNumero()+

" removido com sucesso!"); break;

}

36

FilaPrioridade01 (4)case 3: // Listar tudo

{ todos = filaP.getEnumeration(); while (todos.hasMoreElements ())

{ System.out.println(""); data = (DataArea)todos.nextElement();

data.imprime(); }break;

}case 4: // Sair

break;

default:System.out.println('\n' + "Opção inválida!");

} } }}

37

Exemplo de uso de Fila de Prioridade em Simulação de Eventos Discretos

Uma simulação de eventos discretos servirá para ilustrar um emprego das filas de prioridade

Etapas da simulação Geração do modelo matemático Programa para avaliação do modelo

Sistemas possuem: Estados Eventos (mudanças de estado)

38

Ambiente escolhido para a simulação

Atendimento a clientes em um caixa de banco

O estado do sistema pode ser caracterizado por: Estado do atendente de caixa (ocupado,

desocupado) Número de clientes na fila

39

Modelo de fila de banco

40

Características do Modelo

Eventos Tipo

Chegada (arrival) Partida (departure)

Tempo

Association (utilizada para fazer comparações de prioridade com um atributo chave em vez de com todo o objeto) Tempo (chave) Tipo (valor)

41

Implementação do exemplo (1)

Simulação de sistema composto de: Fila Atendente

A classe Event representa os eventos em simulação

Uma fila de prioridade simulará o atendimento e a prioridade será por tempo

42

Implementação do exemplo (2)

A classe Simulation contém uma fila de prioridade eventList que armazena os eventos

O estado do sistema é retratado pelas variáveis: serverBusy (atendente ocupado sim/não ?) numberInQueue (número de clientes

aguardando atendimento)

43

Implementação do exemplo (3)O método run implementa a simulação e recebe um argumento timeLimit (tempo total da simulação)A chegada de clientes será modelada por instâncias da classe ExponentialRV (geradora de pseudo aleatórios): serviceTime (tempo de um atendimento) interArrivalTime (intervalo entre chegaadas)

A interface RandomVariable tem o método nextDouble que busca um novo valor que neste exemplo teve distribuição com média 100 para ambas as variáveis

44

Implementação do exemplo (4)

Fila inicialmente vazia

Um cliente chega no tempo zero

Repetição até que a lista de eventos fique vazia

Cada iteração retira um elemento da fila de prioridade

Quando o tempo do evento a ser atendido ultrapasse timeLimit termina a simulação

Os eventos podem ser de chegada ou de partida

45

Implementação do exemplo (5)

Atendente desocupado torna-se ocupado na chegada de um cliente disparando o gerador de tempo de atendimento e calculando o tempo de saída correspondente

Atendente ocupado faz aumentar numberInQueue

Depois de cada chegada dispara o gerador de tempo para nova chegada

46

Implementação do exemplo (6)

Evento de saída e fila vazia tornam atendente desocupado

Evento de saída e fila não vazia chamam o próximo na fila disparando o gerador de tempo de atendimento e calculando o tempo de saída correspondente

47

Lembrete: Classe Associationpublic class Association extends AbstractObject{ protected Comparable key; protected Object value; public Association (Comparable key, Object value) {

this.key = key;this.value = value;

} public Association (Comparable key)

{ this (key, null); } public Comparable getKey ()

{ return key; } public Object getValue ()

{ return value; } protected int compareTo (Comparable object) {

Association association = (Association) object;return key.compare (association.getKey ());

}}

48

Classe Event// pgm11_22.txtpublic class Simulation{ static class Event

extends Association {

public static final int arrival = 0;public static final int departure = 1;

Event (int type, double time) { super (new Dbl (time), new Int (type)); }

double getTime () { return ((Dbl) getKey ()).doubleValue (); }

int getType () { return ((Int) getValue ()).intValue (); }

} }

49

Classe Simulation: Inicialização

// pgm11_23.txtpublic class Simulation{ PriorityQueue eventList = new LeftistHeap ();

public void run (double timeLimit) {

boolean serverBusy = false;int numberInQueue = 0;RandomVariable serviceTime = new ExponentialRV (100.);RandomVariable interArrivalTime = new ExponentialRV (100.);eventList.enqueue (new Event (Event.arrival, 0));

50

Classe Simulation: Tratamento do evento de chegadawhile (!eventList.isEmpty ()){ Event event = (Event) eventList.dequeueMin (); double t = event.getTime (); if (t > timeLimit)

{ eventList.purge (); break; } switch (event.getType ()) { case Event.arrival:

if (!serverBusy){ serverBusy = true; eventList.enqueue (new Event(Event.departure,

t + serviceTime.nextDouble ()));}else ++numberInQueue;eventList.enqueue (new Event (Event.arrival, t + interArrivalTime.nextDouble ()));break;

51

Classe Simulation: Tratamento do evento de partida

case Event.departure:if (numberInQueue == 0) serverBusy = false;else{ --numberInQueue; eventList.enqueue (new Event(Event.departure,

t + serviceTime.nextDouble ()));}break;

}}

} // ...}

Implementação C++

53

Implementação

54

Definições das Classes PriorityQueue e MergeablePriorityQueue

// pgm11_01.cpp

class PriorityQueue : public virtual Container

{

public:

virtual void Enqueue(Object&) = 0;

virtual Object& FindMin() const = 0;

virtual Object& DequeueMin() = 0;

};

class MergeablePriorityQueue : public virtual PriorityQueue

{

public:

virtual void Merge(MergeablePriorityQueue&) = 0;

};

55

Definição da Classe BinaryHeap

// pgm11_02.cpp

class BinaryHeap : public PriorityQueue

{

Array<Object*> array;

public:

BinaryHeap(unsigned int);

~BinaryHeap();

// ...

};

56

Definições da Função Membro Purge e do Construtor e Destrutor da Classe BinaryHeap

// pgm11_03.cppBinaryHeap::BinaryHeap(unsigned int length) :

array(length, 1){}

void BinaryHeap::Purge(){

if(IsOwner ()){

for(unsigned int i = 1; i < count + 1; ++i)delete array[i];

}count = 0;

}BinaryHeap::~BinaryHeap()

{ Purge (); }

57

Método enqueue da classe BinaryHeap

• Como o heap resultante da inclusão deve ser uma árvore completa só existe um local para a inclusão

• Este local (vazio ou buraco) vai “subir” no heap até encontrar seu ligar, deixando para baixo os valores menores do que o objeto o incluir no heap

• A “subida” no heap é feita buscando-se a posição do array obtida da divisão por dois da posição corrente

• Quando o buraco parar de “subir” nele inclui-se o objeto

58

Definição da Função Membro Enqueue da Classe BinaryHeap

// pgm11_04.cpp

void BinaryHeap::Enqueue(Object& object)

{

if(count == array.Length())

throw domain_error("priority queue is full");

++count;

unsigned int i = count;

while(i > 1 && *array[i / 2] > object)

{

array[i] = array[i / 2];

i /= 2;

}

array[i] = &object;

}

59

Definição da Função membro FindMin

// pgm11_05.cpp

Object& BinaryHeap::FindMin() const

{

if(count == 0)

throw domain_error("priority queue is empty");

return *array[1];

}

60

Método dequeue da classe BinaryHeap

O elemento a ser removido é o da raiz do heapO objeto que estava no último nó do heap deve procurar seu lugar no heap pois esse nó vai desaparecerInicia-se pela raiz, agora vazia, testando-se seus dois filhos para verificar o menorSe o objeto que estava no último nó for menor que os filhos da raiz termina a repetiçãoCaso contrário a raiz recebe o menor de seus dois filhos que passa a ser a raiz do heap corrente a pesquisarQuando a repetição termina a raiz no heap corrente recebe o objeto que estava no último nó

61

Definição da Função Membro DequeueMin da Classe BinaryHeap (1)

// pgm11_06.cppObject& BinaryHeap::DequeueMin(){

if(count == 0)throw domain_error("priority queue is empty");

Object& result = *array[1];Object& last = *array[count];--count;unsigned int i = 1;

62

Definição da Função Membro DequeueMin da Classe BinaryHeap (2)

while(2 * i < count + 1){

unsigned int child = 2 * i;if(child + 1 < count + 1 && *array[child + 1]

< *array[child])

child += 1;if(last <= *array[child])

break;array[i] = array[child];i = child;

}array[i] = &last;return result;

}

63

Definição da Classe LeftistHeap

// pgm11_07.cppclass LeftistHeap :

public BinaryTree,public MergeablePriorityQueue

{unsigned int nullPathLength;void SwapContents(LeftistHeap&);

public:LeftistHeap();LeftistHeap(Object&);LeftistHeap& Left() const;LeftistHeap& Right() const;void Merge(MergeablePriorityQueue&);// ...

};

64

Definição da Função Membro Merge da Classe LeftistHeap

// pgm11_08.cppvoid LeftistHeap::Merge(MergeablePriorityQueue& queue){

LeftistHeap& arg = dynamic_cast<LeftistHeap&> (queue);if(IsEmpty ())

SwapContents(arg);else

if(!arg.IsEmpty()){

if(*key > *arg.key)SwapContents(arg);

Right().Merge(arg);if(Left().nullPathLength < Right().nullPathLength)

Swap(left, right);nullPathLength = 1 + Min(Left().nullPathLength,

Right().nullPathLength);}

}

65

Definição da Função Membro Enqueue da Classe LeftistHeap

// pgm11_09.cpp

void LeftistHeap::Enqueue(Object& object)

{

LeftistHeap heap(object);

Merge(heap);

}

66

Definição da Função Membro FindMin da Classe LeftistHeap

// pgm11_10.cpp

Object& LeftistHeap::FindMin() const

{

if(IsEmpty ())

throw domain_error("priority queue is empty");

return *key;

}

67

Definição da Função Membro DequeueMin da Classe LeftistHeap// pgm11_11.cppObject& LeftistHeap::DequeueMin(){

if(IsEmpty())throw domain_error("priority queue is empty");

Object& result = *key;LeftistHeap& oldLeft = Left();LeftistHeap& oldRight = Right();key = 0;left = 0;right = 0;SwapContents(oldLeft);delete &oldLeft;Merge(oldRight);delete &oldRight;return result;

}

68

Definição da Classe BinomialTree

// pgm11_12.cpp

class BinomialTree : public GeneralTree

{

void SwapContents(BinomialTree&);

public:

BinomialTree(Object&);

void Add(BinomialTree&);

BinomialTree& Subtree(unsigned int) const;

};

69

Definição da Função Membro Add da Classe BinomialTree

// pgm11_13.cpp

void BinomialTree::Add(BinomialTree& tree)

{

if(degree != tree.degree)

throw invalid_argument("incompatible degrees");

if(*key > *tree.key)

SwapContents(tree);

AttachSubtree(tree);

}

70

Definição da Classe BinomialQueue

// pgm11_14.cppclass BinomialQueue : public MergeablePriorityQueue{

LinkedList<BinomialTree*> list;BinomialTree& FindMinTree() const;void AddTree(BinomialTree&);void RemoveTree(BinomialTree&);static BinomialTree* Sum( BinomialTree*,

BinomialTree*, BinomialTree*);static BinomialTree* Carry( BinomialTree*,

BinomialTree*, BinomialTree*);

public:BinomialQueue();~BinomialQueue();// ...

};

71

Definições da Função Membro AddTree e RemoveTree da Classe BinomialQueue

// pgm11_15.cpp

void BinomialQueue::AddTree(BinomialTree& tree)

{

list.Append(&tree);

count += tree.Count();

}

void BinomialQueue::RemoveTree(BinomialTree& tree)

{

list.Extract(&tree);

count -= tree.Count();

}

72

Definições da Função Membro FindMinTree e FindMin da Classe BinomialHeap// pgm11_16.cppBinomialTree& BinomialQueue::FindMinTree() const{

ListElement<BinomialTree*> const* ptr;BinomialTree* minTree = 0;for(ptr = list.Head(); ptr != 0; ptr = ptr->Next()){

BinomialTree* tree = ptr->Datum();if(minTree == 0 || tree->Key() < minTree->Key())

minTree = tree;}return *minTree;}Object& BinomialQueue::FindMin() const

{if(count == 0)

throw domain_error("priority queue is empty");return FindMinTree().Key();

}

73

Definição da Função Membro Merge da Classe BinomialQueue (1)

// pgm11_17.cppvoid BinomialQueue::Merge(MergeablePriorityQueue& queue){

BinomialQueue& arg = dynamic_cast<BinomialQueue&> (queue);LinkedList<BinomialTree*> oldList = list;list.Purge();count = 0;ListElement<BinomialTree*> const* p = oldList.Head();ListElement<BinomialTree*> const* q = arg.list.Head();BinomialTree* carry = 0;

74

Definição da Função Membro Merge da Classe BinomialQueue (2)for(unsigned int i = 0; p || q || carry; ++i) {

BinomialTree* a = 0;if(p && p->Datum()->Degree() == i) {

a = p->Datum();p = p->Next();

}BinomialTree* b = 0;if(q && q->Datum()->Degree() == i) {

b = q->Datum();q = q->Next();

}BinomialTree* sum = Sum(a, b, carry);if(sum)

AddTree(*sum);carry = Carry(a, b, carry);

}arg.list.Purge();arg.count = 0;

}

75

Definições da Função Membro Sum e Carry da Classe BinomialQueue (1)

// pgm11_18.cppBinomialTree* BinomialQueue::Sum( BinomialTree* a,

BinomialTree* b, BinomialTree* c)

{if(a && !b && !c)

return a;else if(!a && b && !c)

return b;else if(!a && !b && c)

return c;else if(a && b && c)

return c;else

return 0;}

76

Definições da Função Membro Sum e Carry da Classe BinomialQueue (2)

BinomialTree* BinomialQueue::Carry( BinomialTree* a, BinomialTree*

b, BinomialTree*

c){

if(a && b && !c){

a->Add(*b);return a;

}else if(a && !b && c)

{a->Add(*c);return a;

}

77

Definições da Função Membro Sum e Carry da Classe BinomialQueue (3)

else if(!a && b && c) {

b->Add(*c);return b;

}else if(a && b && c)

{a->Add(*b);return a;

}else

return 0;}

78

Definição da Função Membro Enqueue da Classe BinomialQueue

// pgm11_19.cpp

void BinomialQueue::Enqueue(Object& object)

{

BinomialQueue queue;

queue.AddTree(*new BinomialTree(object));

Merge(queue);

}

79

Definição da Função Membro DequeueMin da Classe BinomialQueue (1)

// pgm11_20.cppObject& BinomialQueue::DequeueMin(){

if(count == 0)throw domain_error("priority queue is empty");

BinomialTree& minTree = FindMinTree();RemoveTree(minTree);

BinomialQueue queue;while(minTree.Degree() > 0){

BinomialTree& child = minTree.Subtree(0);minTree.DetachSubtree(child);queue.AddTree(child);

}Merge(queue);

80

Definição da Função Membro DequeueMin da Classe BinomialQueue (2)

Object& result = minTree.Key();

minTree.RescindOwnership();

delete &minTree;

return result;

}