·
Cursos Gerais ·
Teoria das Estruturas 2
Envie sua pergunta para a IA e receba a resposta na hora
Prefere sua atividade resolvida por um tutor especialista?
- Receba resolvida até o seu prazo
- Converse com o tutor pelo chat
- Garantia de 7 dias contra erros
Texto de pré-visualização
Lista de Prioridades HEAP Prof Kennedy Lopes Universidade Federal do Semiarido 6 de abril de 2022 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 1 20 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 2 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Exemplo Nova estrutura idealizada Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Exemplo Nova estrutura idealizada Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Exemplo Nova estrutura idealizada Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Exemplo Nova estrutura idealizada Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 Implementacoes Metodos Lista nao ordenada Lista Ordenada Heap Os dados formam uma lista nao ordenada com n nos Complexidades Selecao On Insercao O1 Remocao On Alteracao On Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 5 20 Implementacoes Metodos Lista nao ordenada Lista Ordenada Heap Os dados formam uma lista ordenada em ordem decrescente de suas prioridades Complexidades Selecao O1 Insercao On Remocao O1 Alteracao On Necessita de uma ordenacao na fase de construcao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 5 20 Implementacoes Metodos Lista nao ordenada Lista Ordenada Heap Os dados podem ser visualizados como uma arvore binaria completa T As prioridade sao organizadas em torno dos nıveis dessa arvore Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 5 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Exemplo Construir uma HEAP com as entradas abaixo 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 7 20 Exemplo Verifique qualis sequˆencias sao HEAP 1 33 2 32 3 28 4 31 5 29 6 26 7 25 8 30 9 27 1 33 2 32 3 28 4 31 5 26 6 29 7 25 8 30 9 27 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 8 20 Propriedades Para um determinado elemento i Pai de i e i2 Filho esquerdo e i 2 Filho direito e i 2 1 1 2 3 4 5 6 7 8 95 60 PAI 78 39 Filho Esquerdo 28 Filho Direito 66 70 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 9 20 Propriedades Para um determinado elemento i Pai de i e i2 Filho esquerdo e i 2 Filho direito e i 2 1 1 2 3 4 5 6 7 8 95 60 PAI 78 39 Filho Esquerdo 28 Filho Direito 66 70 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 9 20 Propriedades Para um determinado elemento i Pai de i e i2 Filho esquerdo e i 2 Filho direito e i 2 1 1 2 3 4 5 6 7 8 95 60 PAI 78 39 Filho Esquerdo 28 Filho Direito 66 70 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 9 20 Propriedades Para um determinado elemento i Pai de i e i2 Filho esquerdo e i 2 Filho direito e i 2 1 1 2 3 4 5 6 7 8 95 60 PAI 78 39 Filho Esquerdo 28 Filho Direito 66 70 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 9 20 Alteracao de Prioridade Ao alterar a prioridade de um no e necessario rearrumar a Heap para que ela respeite as prioridades Um no que tem a prioridade aumentada precisa subir na arvore Um no que tem a prioridade diminuıda precisa descer na arvore Exemplo Mudar a prioridade de 66 para 98 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Exemplo Mudar a prioridade de 95 para 37 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 10 20 Alteracao de Prioridade Ao alterar a prioridade de um no e necessario rearrumar a Heap para que ela respeite as prioridades Um no que tem a prioridade aumentada precisa subir na arvore Um no que tem a prioridade diminuıda precisa descer na arvore Exemplo Mudar a prioridade de 66 para 98 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Exemplo Mudar a prioridade de 95 para 37 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 10 20 Alteracao de Prioridade Ao alterar a prioridade de um no e necessario rearrumar a Heap para que ela respeite as prioridades Um no que tem a prioridade aumentada precisa subir na arvore Um no que tem a prioridade diminuıda precisa descer na arvore Exemplo Mudar a prioridade de 66 para 98 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Exemplo Mudar a prioridade de 95 para 37 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 10 20 Exemplo Mudar a prioridade de 66 para 98 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 11 20 Exemplo Mudar a prioridade de 95 para 37 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 12 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Exemplo de insercao Inserir o elemento 15 na Heap abaixo 1 11 2 5 3 8 4 3 5 4 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 14 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Exemplo de remocao Remova o elemento da Heap abaixo 1 11 2 05 3 08 4 03 5 04 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 16 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Exemplo Contrucao de uma Heap Construa uma Heap a partir da lista L abaixo L 28 33 39 60 66 70 78 95 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 18 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Resumo das complexidade da Heap Operacao Lista Lista Ordenada Arvore balanceada Heap Selecao On O1 Ologn O1 Insercao O1 On Ologn Ologn Remocao On O1 Ologn Ologn Construcao On On logn Ologn On Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 20 20
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
Lista de Prioridades HEAP Prof Kennedy Lopes Universidade Federal do Semiarido 6 de abril de 2022 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 1 20 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 2 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Exemplo Nova estrutura idealizada Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Exemplo Nova estrutura idealizada Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Exemplo Nova estrutura idealizada Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 Prioridades Algumas aplicacoes precisam recuperar rapidamente um dado de maior prioridade Exemplo Lista de tarefas A cada momento devese executar a tarefa com maior prioridade Selecionar a tarefa mais prioritaria de uma lista e retirala da lista Prioridades podem mudar Novas tarefas podem chegar e precisam ser acomodadas Exemplo Nova estrutura idealizada Os dados possuem prioridades de acesso Essa prioridade modifica com o decorrer do tempo Seria interessante manter o dado mais acessado em posicao de destaque Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 3 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 HEAP Lista de Prioridade Definicao Representa uma tabela na qual cada um de seus dados esta associado a uma prioridade Objetivo Descrever uma estrutura de dados que realize as operacoes abaixo eficientemente Selecao do elemento de maior prioridade Insercao de um elemento com prioridade especıfica Remocao do dado de maior prioridade Alteracao de prioridade de um dado Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 4 20 Implementacoes Metodos Lista nao ordenada Lista Ordenada Heap Os dados formam uma lista nao ordenada com n nos Complexidades Selecao On Insercao O1 Remocao On Alteracao On Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 5 20 Implementacoes Metodos Lista nao ordenada Lista Ordenada Heap Os dados formam uma lista ordenada em ordem decrescente de suas prioridades Complexidades Selecao O1 Insercao On Remocao O1 Alteracao On Necessita de uma ordenacao na fase de construcao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 5 20 Implementacoes Metodos Lista nao ordenada Lista Ordenada Heap Os dados podem ser visualizados como uma arvore binaria completa T As prioridade sao organizadas em torno dos nıveis dessa arvore Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 5 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Caracterısticas HEAP Lista Linear vetor composta de elementos com chaves s1 s2 sn As chaves representam as prioridades Nao existem dois elementos com a mesma prioridades Heap Maximo Chaves s1 sn sendo si si2 Heap Mınimo Chaves s1 sn sendo si si2 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 6 20 Exemplo Construir uma HEAP com as entradas abaixo 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 7 20 Exemplo Verifique qualis sequˆencias sao HEAP 1 33 2 32 3 28 4 31 5 29 6 26 7 25 8 30 9 27 1 33 2 32 3 28 4 31 5 26 6 29 7 25 8 30 9 27 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 8 20 Propriedades Para um determinado elemento i Pai de i e i2 Filho esquerdo e i 2 Filho direito e i 2 1 1 2 3 4 5 6 7 8 95 60 PAI 78 39 Filho Esquerdo 28 Filho Direito 66 70 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 9 20 Propriedades Para um determinado elemento i Pai de i e i2 Filho esquerdo e i 2 Filho direito e i 2 1 1 2 3 4 5 6 7 8 95 60 PAI 78 39 Filho Esquerdo 28 Filho Direito 66 70 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 9 20 Propriedades Para um determinado elemento i Pai de i e i2 Filho esquerdo e i 2 Filho direito e i 2 1 1 2 3 4 5 6 7 8 95 60 PAI 78 39 Filho Esquerdo 28 Filho Direito 66 70 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 9 20 Propriedades Para um determinado elemento i Pai de i e i2 Filho esquerdo e i 2 Filho direito e i 2 1 1 2 3 4 5 6 7 8 95 60 PAI 78 39 Filho Esquerdo 28 Filho Direito 66 70 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 9 20 Alteracao de Prioridade Ao alterar a prioridade de um no e necessario rearrumar a Heap para que ela respeite as prioridades Um no que tem a prioridade aumentada precisa subir na arvore Um no que tem a prioridade diminuıda precisa descer na arvore Exemplo Mudar a prioridade de 66 para 98 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Exemplo Mudar a prioridade de 95 para 37 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 10 20 Alteracao de Prioridade Ao alterar a prioridade de um no e necessario rearrumar a Heap para que ela respeite as prioridades Um no que tem a prioridade aumentada precisa subir na arvore Um no que tem a prioridade diminuıda precisa descer na arvore Exemplo Mudar a prioridade de 66 para 98 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Exemplo Mudar a prioridade de 95 para 37 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 10 20 Alteracao de Prioridade Ao alterar a prioridade de um no e necessario rearrumar a Heap para que ela respeite as prioridades Um no que tem a prioridade aumentada precisa subir na arvore Um no que tem a prioridade diminuıda precisa descer na arvore Exemplo Mudar a prioridade de 66 para 98 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Exemplo Mudar a prioridade de 95 para 37 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 10 20 Exemplo Mudar a prioridade de 66 para 98 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 11 20 Exemplo Mudar a prioridade de 95 para 37 1 95 2 60 3 78 4 39 5 28 6 66 7 70 8 33 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 12 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Insercao Procedimentos Tabela com n elementos Inserir novo elemento na posicao n 1 Compare o elemento no final do heap e facao subir ate sua posicao correta Se estiver em ordem a insercao terminou Se nao estiver em ordem troque com o pai e repita o processo ate terminar ou chegar a raiz Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 13 20 Exemplo de insercao Inserir o elemento 15 na Heap abaixo 1 11 2 5 3 8 4 3 5 4 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 14 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Remocao Procedimento Retirase sempre a raiz elemento com maior prioridade Coloque na raiz o ultimo elemento da Heap e facao descer ate a posicao correta Compare o elemento com seus filhos Se estiver em ordem a remocao terminou Se nao estiver em ordem troque com o maior filho e repita o processo ate terminar ou chegar a um no folha Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 15 20 Exemplo de remocao Remova o elemento da Heap abaixo 1 11 2 05 3 08 4 03 5 04 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 16 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Construcao de Lista de Prioridades Dado uma lista L de elementos para o qual se deseja construir uma heap H ha trˆes alternativas 1 Considerar uma heap vazia e inserir elemento a elemento 2 Considerar que a lista L ja representa uma Heap e corrigir as prioridades 21 Considerar os nos folhas corretos 22 Corrigir os nos internos realizando descidas 3 Link Corrigir subir os nos a partir dos nos folhas Incluindo processo de ordenacao Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 17 20 Exemplo Contrucao de uma Heap Construa uma Heap a partir da lista L abaixo L 28 33 39 60 66 70 78 95 Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 18 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Ordenacao a partir de uma Heap A partir de uma heap e possıvel ordenar os dados fazendo trocas O maior elementoraiz e trocado com o ultimo elemento Esse elemento ja se encontra ordenado Considerar que o vetor possui agora n 1 posicoes e descer a nova raiz ate sua posicao correta na Heap Repetir os passos anteriores n 1 vezes Complexidade dessa ordenacao e de On log n Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 19 20 Resumo das complexidade da Heap Operacao Lista Lista Ordenada Arvore balanceada Heap Selecao On O1 Ologn O1 Insercao O1 On Ologn Ologn Remocao On O1 Ologn Ologn Construcao On On logn Ologn On Prof Kennedy Lopes UFERSA Lista de Prioridades 6 de abril de 2022 20 20