Embed Size (px)
Citation preview
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;
}
