Projeto e Análise de Algoritmos - Aula 07 - A estrutura de dados heap

[Música] o olá pessoal sejam bem vindos à nossa aula número 7 do projeto e análise algoritmos nessa aula veremos a estrutura da do chip primeiro vamos ter a definição do que um chip como manter a propriedade do the sheep em finalmente como construir uma equipe b que o chip é uma estrutura da água que pode ser visualizada como uma árvore na área quase completa ele tem algumas propriedades árvore completa até o penúltimo nível tá no último nível as folhas está sempre mais esquerda possível e o conteúdo de um novo também deve ser maior ou igual

ao conteúdo dos nossos na sua árvore raissa nele isso para definir um mas a equipe também se une chip a única diferença vai estar nessa última propriedade em um lugar é maior ou igual vai ser menor ou igual o conteúdo de um menor ou igual ao conteúdo dos nossos na sua árvore raissa nele o que vai definir um microchip daqui a pouco vamos ver um é sempre essas condições a essas propriedades vão garantir que esse chip possa ser armazenada no vector vamos chamar receber também de everton que representou equipe essa vitória vai ter nessa posição

até a posição e me então agora nós temos a ver um exemplo vejam vocês a árvore aqui apenas os seguintes valores nos nossos 27 em 1814 etc etc vamos verificar se essa árvore cumprir a propriedade de chip então primeiro amor e completá tupi no último nível está a completar até o penúltimo nível no último nível as folhas estavam mais cana possível sim pensou duas folhas estão mais cana possível o conteúdo de um noel maio é maior ou igual ao conteúdo dos na sua raiz anelli por exemplo o 27 é maior a todos os nós da

sub árvores dele ele tem duas sob árvores né 27 maior ator sesi assim e assim o mesmo que a gente tem que verificar para todos os noves 8 maior que sua sub árvores é 14 maior é 17 maior em 18 maior do semae o que não tem nada embaixo né então a gente tem que verificar isso para todos não se a propriedade é válida para todos nos água então aqui agora é uma das coisas que fala que falamos antes e que essas propriedades garantem de que eu posso usar um vetor para poder representar essa árvore

não precisa de criar exatamente uma árvore fisicamente numa árvore eu posso usar um vector para apresentar isso qualquer idéia então a idéia é colocar esses valores por níveis então vou colocar o 27 na posição 1 do vertedouro 18 na posição 21 14 na posição 3 e assim por diante por níveis tá eu como não tem nenhum buraco no meio dessa árvore nem é vocês não vão ter um buraco no meio no repertório estão aqui está no nosso sector 27 primeiro depois 18 14 7 12 3 e 11 15 e 26 por níveis tá bom se

eu tenho uma posição por exemplo eu tenho o elemento que está na posição do vetor que o 18 com amplos saberia onde estão os filhos dele ok na água ea gente sabe mas no vetor como que a rês sabe em que posição está o filho esquerdo em que posição está o filho o direito se a gente olha aqui o nó número 2 onde está o filho esquerdo está no 4 na posição 4 eo filho direito na posição 5 que operação a gente poderia fazer com esse dois para conseguir encontrar o filho direito o filho que

ela ofende o direito a gente multiplica as questões aqui aqui nesses dois mais 11 filhos que elas em 2005 o fim do direito foi assim mais um essa propriedade vai se cumprir para qualquer novo na verdade então para qualquer um e dois em dois se vai estar o filho escreve o daee em 2 e mais chuva estar o filho direito nei e agora como é que eu calculei a posição do pai onde que seu pai o pai de qualquer não a gente simplesmente pode fazer o inverso no lugar de multiplicar a gente dividir por dois

o santos só tem que ter cuidado com os números parecem parece né para isso então a gente pode usar o chão o pai está na posição e ele viveu por dois chão mas eu seria a posição do pai então por exemplo pai dono 6 está na posição 3 tá certo para todo nu e d2 atm essa propriedade vai ser cumprir a na posição e sobre dois vai ser maior ou igual a ana posicionem porque o pai para o maxixe machine pe o pai sempre tem que ser maior que o filho isso vai garantir que o

maior elemento também está onde está na raiz o maior elemento e toda árvore sempre vai estar na raiz tá bom uma outra coisa que a gente pode ver nessa árvore eo nível nessas de quem seria o nível certo nível o nível 2 o nível 3 tatá nível pena a verdade então vai ter a gente pode fazer um cálculo ele pode ter ele vai ter exatamente dois apenas exceto o último nível se ele não está completa né o último nível não estiver completa então por exemplo o nível 2 quantos nos têm nível do estamos aqui ele

tem quatro que doença elevando a pé do elevador 24 uma outra característica uma outra definição que temos que ver é a altura altura de um nome e é o maior cumprimento de um caminho de areia tem uma folha em outras palavras é o número destas no caminho mais longo o desenho até uma folha vejamos um exemplo mas antes de ver o exemplo a gente pode ferver o caso mais básico em qualquer altura das folhas as folhas não tem nada mais imagens a altura delas e serão um outro sempre qualquer altura do número 2 de senão

daqui a gente tem que procurar qualquer um caminho mais longo o caminho mais longo êsse de kim e seu ensino e aqui estão à altura dele e 2 certo a gente também poderia tentar demonstrar que a altura de um nome qualquer e shaun de longe de emana / e considerando isso a altura da raiz seria o de longe de m2 e vai ser um iê a mesma altura da árvore também na altura da árvore chão de longe de m então vejamos aqui nesse exemplo no qual seria a altura da árvore a nossa árvore ele tem

nove elementos então o mp9 longevas e dois de nove e três em alguma coisa portanto altura da árvore 37 de altura da árvore e 3 e agora vamos ver uma operação que é necessária para manter a propriedade dom que as propriedades em que vejamos um exemplo temos aqui uma árvore ele é quase o chip porque tem um elemento que não sabe só essa propriedade erechim único elemento nesse exemplo que não satisfaça propriedade energia é a raiz o que a gente poderia fazer para poder arrumar esse é esse chip esse é a árvore que não é

quase um chip então o primeiro que temos que pensar em como eu posso arrumar isso a idéia é deixar ele escorregar e se hoje para baixo até colocar ele na posição certa também aqui temos a representação árvore e aqui temos a representação everton não temos aqui os elementos representados por nível não 8 depois surge 18 14 depois dos 7 2 e 3 e 11 e assim por diante é que vamos fazer então primeiro vamos fazer em comparar o 8 com seus filhos os filhos ongs 8 14 aí encontramos com que o maior deles é o

18 e vamos trocar vamos descer o 8 para baixo vamos trocar ele pelo maior dos seus filhos nesse caso é o 18 trocamos seles e agora fazemos o mesmo com o próximo nó como 2 certo comparamos o nó 2 com 145 com seus filhos e encontramos qual é o maior dos filhos para poder trocar com ele o maior e odense 7 então vamos trocar como 17 fazemos o mesmo agora como no 4 temos os filhos dele çom 15 e 16 trocamos com o maior e eu temos esse resultado e agora conseguimos o que queríamos colocar

o 8 no lugar certo e fazer com que o chip cumpra todas as propriedades para todos nós então para transformar um vetor num chip bastou rebaixar nesse centro 8 até eles a ti só será propriedade de chip fazer com que ele desça organismo que faz isso o algoritmo max fay ele recebe um vector a deu até posicionei-me e o indiciei tal que as árvores com raízes nos filhos esquerdo e direito do nó e são mais equipe faz as primeiras linhas o algoritmo que vão fazer e verificar que o maior se o oeste mato que está

na posicione o elemento questionar parte esquerda ou na parte direita então o primeiro passo é encontrar qualquer posição do elemento da esquerda e 2006 o elemento da direita e 2006 e mais um depois disso vamos verificar quem é o maior o elemento que está o o elemento que está na posição esquerda ou provimento e é isso que está sendo feito aqui e aí vamos encontrar aqui o maior deles posteriormente uma vez que encontramos o maior em 32 agora vou comparar com o elemento que está na posição direita e é isso que está sendo feito aqui

finalmente é depois de ter então encontrado qualquer oposição à gestão o elemento maior é definir se quer o filho direito aí finalmente vamos chamar o masc fay agora com a posição maior mas antes de fazer isso vamos trocar o elemento da oposição que está na rússia o maior como elemento que está na posição e certo que é feito na linha 9 e finalmente chamamos o max fight com o elemento maior possa trocar este momento como possível maior suponha que vocês sabem qual é a altura do ano em que você sabe que o consumo de tempo

de desse algoritmo e tvh para uma entrada com um conseguiria com exceção da recorrência então para esse algoritmo iraque eo vôo ou de um porque não sabemos que uma hora eu ou de um tratado e onde eu vim aqui porque não sabemos se vai entrar num 17 por exemplo 1 415 por isso que esse é isso 11 depois no 8 é t-19 eu dôo e na linha 10 a gente sabe que quando o max foi chamado ele vai descendo um nível por nível certo então na verdade é que vai ser menor ou igual a tv

h - 1 uma vez que é altura de maior e pagar menos um uma coisa que poderíamos falar e pensar de artes e fazer análises em fazer análises se a gente lembra como que funciona o organismo mais que fay a gente vê de que ele vai fazendo com que o valor que queremos colocar um pouquinho certa leveza de um eo nível e no final ele vai ter uma complexidade que depende da altura da árvore no pior dos casos ele vai vencer todos os níveis até chegar uma folha então a gente já tem uma idéia mais

ou menos enquanto o consumo de do arvorismo fazendo as contas a 5º a somatória superliga vai ser menor ou igual a ter ao menos um mas vários teta de 877 que pode ser colocado como tt1 ea gente pode demonstrar que teve h é da ordem de d ou seja o consumo de tempo para uma entrada para um nome qualquer depende da altura dessa árvore cujo nome inicial e como à altura do nome e logo dm sobre então substituindo aqui vamos ter de pagar igual ao de kaká substituindo a vapor logo dm sobre que a gente

já viu na lei anterior que isso aqui é uma coisa que podemos demonstrar para os chips então vamos ter que tirar esse essencial finalmente podemos obter que th e odeia o dm concluindo o consumo do tempo do max fight foi o de longe de vamos ver agora a última operação que a construção de uma equipe a idéia do heroísmo que construir um chip com base no vector quem não é um chip é assim tinha montar o chip a partir das folhas então suponho que eu tenho visto qualquer e eu quero que esse vetor tenha propriedade

de chip então vamos colocar é todos eles só para ter uma idéia a visualização como que ficaria todos eles na árvore tá olhando na árvore que foi montada a partir desse vetor os únicos elementos que compõem a propriedade de chips ou nas folhas então porquê porque ele não tem mais elementos em baixo sérgio então aqui não tem mais elementos que também não então ellison chips eles contam na verdade eles cumprem nas propriedades e chip então que são os elementos desde a posição é mails teto a tn então se eu sei que tu ou se eles

cumprem eu vou começar com aquele que não cumpre o primeiro que não cumprir nessa ordem seria 35 vamos começar com ele comparando aos 35 com os seus filhos aqui temos que encontrar quem que é o maior o maior dos filhos e us 70 então eu vou trocar o 35 com 77 aí vamos continuar com o próximo nó agora é se daqui já está certinha partilha que essa árvore está certinha continuamos com o próximo nó que o no 3 e fazemos o mesmo comparamos no 3 com seus filhos então vemos é esse de compra a propriedade

da equipe não então vou trocar com seu filho maior o filho maior dele é o 71 e agora cumpre as propriedades e chip passamos para o seguinte no 12 fazemos o mesmo olhamos para seus filhos 40 e 80 não está cumprindo a propriedade do chip não então vamos trocar com o filho maior aí vai ficar 80 e 20 e agora ela na parte de baixo o que está certo não tem mais nada então tá tudo certo vamos para o próximo não o nó 40 e comparamos com seus filhos 80 e 71 contra propriedade de chip

não compre então vamos trocar com seu filho maior então vai ficar 80 e 40 foram trocados ou 40 com 80 mas saí ainda tem alguns problemas a gente tem que verificar ensino com seus filhos 40 temos os índios 70 e 20 isso daí ainda não está cumprindo a propriedade da equipe então temos que descer ainda mais ele vamos descer ele então se chocar com maior vai ficar 70 e 40 certo e depois fazemos o mesmo com 40 e os filhos dele que são 21 e 35 cumpra propriedade de chip sim tá bom então já terminei

então na verdade o que estamos fazendo para cada um dos nossos que não é folha o que estamos fazendo e aplicar o algoritmo macfee certo favoritismo que faz isso o algoritmo ir mais à equipe ele não sabe como entrada um vetor a que tendem a possuir um ano será possível mini que ele vai fazer então ele vai percorrer desde a posição n de vídeo por do chão até posição 1 que seriam todos os elementos que não são folhas e ele vai chamar o masc fai como parâmetro e se a gente faz uma análise grosseira disso

a gente poderia falhar assim a linha um consome teta de e mails certo porque ele vai de e mails at1 ea linha 2 portanto ele vai ser e mails ver e cissokho consome mais que faz e acabamos de falar que o máximo que vai consumir o ibdn portanto daria e mail bn no total seria o dn o dn mas se isso fosse uma análise se bem superficial que fizer as contas direitinho uma análise detalhada a gente precisaria contar o número de nós em cada nível e multiplicar pelo custo do masp foi para cada um desses

desses nós tá isso de pé a gente sabe que isso depende da altura do nó se fôssemos essa análise detalhada vamos encontrar que o consumo de tempo o irã mas que na verdade é teta dn então essa foi a nossa aula número 7 sobre a estrutura de dados rio na próxima aula teremos o organismo y aguardo vocês então para a próxima aula [Música] [Música] [Música] [Música]