.. -*- coding: utf-8 -*- Organização =========== Desde sempre, ordenação foi uma grande arte e um laboratório de ideias. Estivemos sendo exposto a várias ideias ao longo do nosso caminho. Nos capítulos anteriores vimos que o Mergesort é muito rápido, consome tempo :math:`\mathtt{\textup{O}(n \lg n)}` em que :math:`\mathtt{n}` é o número de elementos a serem ordenados. O preço de tanta eficiência é a necessidade de espaço para rascunho que pode ser proporcional a :math:`\mathtt{n}`, é o chamado espaço extra :math:`\mathtt{\textup{O}(n)}`. Apesar da modéstia no nome, o Quicksort, no pior caso consome tempo :math:`\mathtt{\textup{O}(n^2)}` e usa espaço extra :math:`\mathtt{\textup{O}(n)}`. Na sua versão recursiva o espaço extra do Quicksort fica meio escondido numa coisa chamada *pilha da recursão*. Já na nossa versão iterativa o espaço extra está explícito na lista usada e que demos o nome de `pilha` devido ao seu comportamento pouco discreto. Bem, verdade seja dita, no dia a dia o Quicksort é muito rápido mesmo e merece o seu nome de batismo. Seu consumo de tempo esperado é :math:`\mathtt{\textup{O}(n \lg n)}` e espaço extra pode ser limitado por :math:`\mathtt{\textup{O}(\lg n)}`. Chegou o momento de testemunharmos como a maneira que **organizarmos os dados** pode impactar de forma surpreendente o consumo de tempo e de espaço de um algoritmo e consequentemente o tempo gasto por uma função que implementa esse algoritmo. |:face_with_raised_eyebrow:| Criaremos uma classe que organiza os elementos de uma lista de uma tal forma que permitirá que projetemos uma função que consome tempo :math:`\mathtt{\textup{O}(n \lg n)}` e espaço extra :math:`\mathtt{\textup{O}(1)}` (!) para ordenar uma lista com :math:`\mathtt{n}` elementos. Objetivos de aprendizagem ------------------------- Uma **estrutura de dados** é a maneira de organizarmos os dados/valores para que sejam manipulados eficientemente por nossos programas. Estudaremos uma estrutura de dados, conhecida como *heap*, que é a base de um algoritmo de ordenação ainda mais sofisticado conhecido como `Heapsort `_ . Esses tais de *heaps* são muito espertos para encontrar um maior ou menor elemento de alguma coleção de valores. Isso diz que *Heaps* são ideias para ajudar a *ordenação por seleção* a encontrar, em cada iteração, um maior elemento de uma sublista. As características de *Heaps* fazem com sejam uma forma de organizarmos objetos em filas com prioridade ou filas priorizadas (`Priority queue `_). .. image:: ./imgs/heap_presents.* :width: 562 :height: 408 :scale: 50 :alt: This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License. :align: center :target: http://xkcd.com/835/ |:thinking:| Para efeito de isenção de responsabilidade... O adjetivo *prioridade* para filas é um certo pleonasmo... Filas de coisas ou objetos naturalmente já indicam que os objetos ou as coisas serão consideradas em alguma ordem. Filas de pessoas dão a ordem em que as pessoas serão atendidas... Prioridade é algo que vem embutido em filas, pelo menos parece... Seleção ------- O problema que continuaremos a tratar é o de ordenar uma lista de elementos. Dizemos que uma lista :math:`\mathtt{v[0{:}n]}` é **crescente** se .. math:: \mathtt{v[0] \leq v[1] \leq v[2] \leq \cdots \leq v[n{-}1].} Como temos feito nos exemplos as listas serão de objetos ``int`` mas elas poderiam ser de ``str`` ou de quaisquer outros objetos que possam atuar como operandos de *operadores relacionais* como ``<``, ``<=``, ``>`` ou ``>=``. **Problema**: Rearranjar os elementos de uma lista ``v[0:n]`` de modo que ela fique crescente. .. image:: ./imgs/ordenacao.* :width: 810 :height: 384 :scale: 50 :alt: Instância de ordenação :align: center O algoritmo que discutiremos é baseado na operação de **seleção** do maior elemento em uma sublista que é prefixo de uma lista: **Problema da seleção**: Dada uma lista ``v`` e um inteiro ``n``, encontrar um índice ``i`` tal que ``v[i]`` é o maior elemento da lista ``v[0:n]``. Esse problema é facilmente resolvido pela função ``selecione_lst()`` que está abaixo. Os números no início das linhas não fazem parte do código e só estão presentes para podermos fazer referência às linhas. .. raw:: html 
     
    def selecione_lst(v, n):
        ''' (list, int) -> int
        RECEBE uma lista v.
        RETORNA um índice i tal que v[i] é o maior elemento de v[0:n]
        '''
    0   imax = n-1
    1   for i in range(n-1):
    2       if v[i] > v[imax]: imax = i
    3   return imax
A correção da função ``selecione_lst()`` é evidente. Assim como é claro que o seu consumo de tempo é :math:`\mathtt{\textup{O}(n)}` em que ``n`` é o argumento que indica o prefixo relevante da lista ``v``, ou seja, seus primeiros ``n`` elementos. O algoritmo central deste capítulo é iterativo. Em cada iteração o maior elemento de uma sublista prefixo da lista ``v`` é selecionado e movido para a última posição da sublista. Como *seleção* é a operação em que o algoritmo se apoia ele é conhecido como **ordenação por seleção**. A seguir está a função ``selecao()`` que implementa essa ideia. .. raw:: html 
   
        def selecao(v):
            '''(list) -> None
            RECEBE uma lista v.
            REARRANJA os elementos de v para que fiquem em ordem crescente.
            '''
        0   n = len(v)
        1   for i in range(n, 1, -1):
                # selecione a posição de um maior elemento da vista v[0:i]
        2       imax = selecione_lst(v, i)
                # mova o maior elemento para a última posição da vista v[0:i]
        3       v[i-1], v[imax] = v[imax], v[i-1]
A razão da função ``selecao()`` fazer o que promete se deve às relações invariantes abaixo. Essas relações invariantes valem, são verdadeiras, no início de cada iteração das linhas 1, 2 e 3: * ``v`` é um arranjo da lista original; * o sufixo ``v[i:n]`` é crescente; e * ``v[0:i]`` :math:`\mathtt{\leq}` ``v[i:n]`` que em palavras significa que para todo elemento ``val1`` em ``v[0:i]`` e para todo elemento ``val2`` em ``v[i:n]`` vale que ``val1`` :math:`\mathtt{\leq}` ``val2``. No início da última iteração temos que :math:`\mathtt{i = 1}` e portanto ``v[1:n]`` é crescente e ``v[0]`` :math:`\mathtt{\leq}` ``v[1:n]``. Portanto ``v`` é crescente. Vamos estimar o consumo de tempo da função ``selecao()``. Vamos supor que cada linha consome 1 unidade de tempo exceto, evidentemente, a linha 2 que consome tempo :math:`\mathtt{\textup{O}(i)}`. .. math:: \begin{array}{ll} \text{linha} & \text{consumo de tempo das execuções das linhas}\\ \hline 0 & = \textup{O}(\mathtt{1}) \\ 1 & = \textup{O}(\mathtt{n}) \\ 2 & = \textup{O}(\mathtt{n}+ \mathtt{(n{-}1)} + \cdots + 1) = \textup{O}\mathtt{(n^2)}\\ 3 & = \textup{O}(\mathtt{n}) \\ \hline \rule[0ex]{0ex}{3ex}% {\text{total}} & = \textup{O}(\mathtt{n^2+2n+1}) = \textup{O}\mathtt{(n^2)} \end{array} A nossa análise independe do caso. É uma análise para todos os casos. O comportamento da função ``selecao()`` é sempre quadrático independentemente da lista de entrada. **Conclusão**. O consumo de tempo da função ``selecao()`` é :math:`\mathtt{\textup{O}(n^2)}` em que :math:`\mathtt{n}` é o número de elementos na sublista considerada. Vemos que a ordenação por seleção não é particularmente rápida para ordenar uma lista. Já vimos algoritmos mais rápidos como Mergesort e o Quicksort. Um fato positivo sobre a ordenação por seleção é de que, como todos os demais algoritmos quadráticos, o espaço extra necessário é constante independentemente do número de elementos da lista. Veremos |:eyes:| como *magicamente* |:mage_tone3:| **organizar** os elementos da lista ``v`` de maneira que a operação de encontrar o maior elemento de uma sublista em cada iteração possa ser feita em tempo *encantado* |:magic_wand:| logarítmico, :math:`\mathtt{\textup{O}(\lg n)}`. em vez de linear, :math:`\mathtt{\textup{O}(n)}`. Com isso, como o algoritmo faz :math:`\mathtt{n}` iterações, chegaremos a mais um algoritmo de consumo de tempo :math:`\mathtt{\textup{O}(n \lg n})`. Esse algoritmo é chamado de Heapsort. Heapsort -------- Descreveremos aqui uma versão da ordenação por seleção que consome tempo :math:`\mathtt{\textup{O}(n \lg n})` mesmo antes de revelar como a maga |:mage_tone5:| fará a sua mágica. |:magic_wand:| A poção principal da mágica é uma estrutura de dados conhecida pelo nome de Heap. Essa estrutura será materializada mais adiante por meio de uma classe de nome ``MaxHeap`` que implementaremos. No momento só precisamos saber que o consumo de tempo do método principal dessa classe opera em tempo logarítmico. Sem mais delongas, aqui está a nossa implementação do Heapsort. .. raw:: html 
    def heapsort(v):
        '''(list) -> None
        RECEBE uma lista v.
        REARRANJA os elementos de v para que fiquem em ordem crescente.
        NOTA. Usa a classe MaxHeap. Adaptação mutadora de heapsort() em
              https://docs.python.org/3/library/heapq.html
        '''
    0   n = len(v)
        # pré-processamento: crie um MaxHeap com elementos de v 
    1   h = MaxHeap()
    2   for item in v: h.insira(item)
        
        # ordenação por seleção
    3   for i in range(n, 1, -1):
            # maior elemento da lista v[0:i] vai para última posição da lista
    4       v[i-1] = h.remova()
Seguem alguns exemplos de execução da função ``heapsort()``. .. raw:: html 
    In [2]: x = [21, 12, 43, 61, 41, 71, 91, 31, 81]
    In [3]: heapsort(x)
    In [4]: x
    Out[4]: [12, 21, 31, 41, 43, 61, 71, 81, 91]

    In [5]: y = ['aa', 'c', 'e', 'aa', 'z', 'a-b', 'ef', 'b', 'a', 'cz']
    In [6]: heapsort(y)
    In [7]: y
    Out[7]: ['a', 'a-b', 'aa', 'aa', 'b', 'c', 'cz', 'e', 'ef', 'z']
Na linha 1 a função ``heapsort()`` prepara a cartola |:tophat:| mágica que será o objeto ``h`` da classe ``MaxHeap``. Na linha 2 os ingredientes, elementos de ``v``, são colocados um a um na cartola |:tophat:| com as palavras mágicas ``h.insira()``. O consumo de tempo de cada operação de colocar um item na cartola, ``h.insere(item)`` é magicamente :math:`\mathtt{\textup{O}(\lg n)}`, em que :math:`\mathtt{n}` é o número de elementos de ``v``. Com isso, concluímos que o consumo de tempo total da linhas 2 e 3 é :math:`\mathtt{\textup{O}(n \lg n})`. Essa é uma fase de **pré-processamento** da função em que estamos apenas preparando o palco para a mágica. Na linha 4 é consumido tempo :math:`\mathtt{\textup{O}(\lg n)}`, em cada iteração, para tirar o maior elemento da cartola. Desta vez a palavra mágica é ``h.remove()``. O maior elemento é então colocado na última posição da vista ``v[0:i]``. Como serão retirados da cartola os :math:`\mathtt{n}` elementos que foram inseridos, o consumo de tempo total das linhas 3 e 4 será, também, :math:`\mathtt{\textup{O}(n \lg n})`. Com isso chegamos a seguinte conclusão: **Conclusão**. O consumo de tempo da função ``heapsort()`` é :math:`\mathtt{\textup{O}(n \lg n)}` em que :math:`\mathtt{n}` é o número de elementos na lista. A única coisa que resta a fazer é revelar como a maga |:mage_tone4:| utiliza a cartola para fazer a mágica. |:magic_wand:| Na próxima seção discutiremos a composição mágica da cartola. Um pouco mais adiante montaremos a nossa fábrica de cartolas mágicas, a classe ``MaxHeap``. Aqui está uma animação do Heapsort. Parece mágica ou não parece? |:man_facepalming:| .. image:: ./imgs/Sorting_heapsort_anim.* :width: 280 :height: 214 :scale: 100 :alt: By RolandH, CC BY-SA 3.0, :align: center :target: https://commons.wikimedia.org/w/index.php?curid=3330798 Heaps ----- Nesta seção desvendaremos os segredos da cartola. |:tophat:| Os segredos foram ingredientes contrabandeados da floresta mágica de Paulo Feofiloff em `Heapsort `_ . Uma árvore em que cada nó tem dois ramos é chamada de binária. Vocês estão vendo os dois ramos saindo de cada nó na árvore abaixo? .. image:: ./imgs/tree_upside_down.* :width: 960 :height: 819 :scale: 20 :alt: Tree :align: center :target: https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1206/lectures/trees/ Um ``heap`` (= monte) é uma árvore binária que pode ser organizada como *max-heap* ou *min-heap*. Trataremos apenas de max-heap, inclusive muitas vezes omitindo o prefixo "max". A terminologia de árvores tem muitos termos herdados das `árvores genealógicas `_ . Uma **árvore binária** é uma estrutura como ilustrada abaixo, onde cada nó pode apresentar até duas filhas ou dois filhos, ou uma filha e uma filho. Vamos denominar de *filha esquerda* e de *filha direita*. .. image:: ./imgs/maxheap.* :width: 887 :height: 465 :scale: 60 :alt: Exemplo de árvore binária max-heap. :align: center O primeiro nó da árvore, o nó 1, é chamado de **raiz**. No exemplo o valor da raiz é o elemento 51. A **filha esquerda** da raiz é o nó 2 que contém o elemento 46 e a **filha direita** é o nó 3 que contém o 17. Para simplificar, vamos muitas vezes dizer apenas que "*as filhas de 51 são 46 e 17*", ou que "*a mãe de 17 é 51*", ou algo parecido. A raiz é o único nó que não tem mãe. Nem todos os nós tem filhas. Nós sem filhas são chamados de **folhas** da árvore. O nome faz sentido, certo?! |:thinking:| O nó 7 é uma folha. Alguns nós podem ter apenas uma filha, como é o caso do nó 6. **Propriedade de uma max-heap**: Uma árvore é um max-heap se para todo nó, exceto a raiz, o valor da mãe é maior ou igual ao valor de suas filhas. A árvore binária da figura anterior é um max-heap já que satisfaz essa propriedade. Por exemplo, o nó 5 tem o valor 41 que é maior ou igual ao valor das suas filhas, nós 10 e 11, que têm os valores 21 e 10. Cada nível :math:`\mathtt{k}` de uma árvore binária possui no máximo :math:`\mathtt{2^k}` nós. O nível 0 tem um :math:`\mathtt{2^0=1}` nó que é a raiz da árvore, o nível 1 tem até :math:`\mathtt{2^1=2}` nós, o nível 2 tem até :math:`\mathtt{2^2=4}` nós, o nível 3 tem até :math:`\mathtt{2^3=8}` nós, etc. No nosso caso, para que a nossa cartola |:tophat:| seja mágica, **apenas** o último nível da árvore não precisa estar completo, pode ter menos que :math:`\mathtt{2^k}` nós. No exemplo o último é o nivel 3 que tem :math:`\mathtt{5 < 2^3=8}` folhas. Árvores binárias em listas -------------------------- Associaremos a numeração dos nós da árvore binária a índices de uma lista como mostrada na figura adiante. A ideia é que olhemos para uma lista, mas enxerguemos |:eyes:| uma árvore. Primeiro consideraremos que o elemento do nó :math:`\mathtt{i}` está na posição de índice :math:`\mathtt{i}` da lista. As relações familiares de um nó :math:`\mathtt{i}` são obtidas através de multiplicações e divisões por 2: * a mãe de :math:`\mathtt{i}` é o nó :math:`\mathtt{i//2}` e * as filhas são o nó :math:`\mathtt{2*i}` e o nó :math:`\mathtt{2*i+1}`. Assim a raiz, que é o nó 1, está na posição de índice 1. As filhas da raiz são os nós 2 e 3 são os elementos nas posições de índice 2 e 3 as netas são os nós 4, 5, 6 e 7 são os elementos ... É através dessa numeração associada a índices e a propriedade de max-heap que organizaremos os valores da nossa lista. .. image:: ./imgs/maxheapLista.* :width: 887 :height: 551 :scale: 60 :alt: Representação de uma árvore binária max heap usando lista. :align: center O elemento da posição de índice 0 da lista será ``None``. Dessa forma o elemento na posição de índice 0 não será considerado pois **não faz parte da árvore**. A adoção dessa numeração, começando do 1, facilita que determinemos a relação de parentesco entre os nós e seus elementos: quem é a mãe de quem ou quem é filha de quem. Se ``f`` é um índice qualquer da árvore então o índice de sua: * mãe é ``f//2``, se ``f`` não for a raiz; * filha esquerda é ``2*f``, se ``f`` tem alguma filha; e * filha direita é ``2*f + 1``, se ``f`` tiver duas filhas. No exemplo anterior temos que: * a mãe do nó ``13`` é ``13//2 = 6``; * a mãe do nó ``6`` é ``6//2 = 3``; * a mãe do nó ``3`` é ``3//2 = 1``; * as filhas do nó ``3`` são ``2*3=6`` e ``2*3+1=7``; * as filhas do nó ``5`` são ``2*5=10`` e ``2*5+1=11``; * a única filha do nó ``6`` é ``2*6=12``; e * os nós ``7``, ``8``, ``9`` , ``10``, ``11``, e ``12`` não tem filhas. Classe MaxHeap -------------- .. image:: ./imgs/Heapsort-example.* :width: 350 :height: 280 :scale: 100 :alt: Heapsort example :align: center :target: https://upload.wikimedia.org/wikipedia/commons/4/4d/Heapsort-example.gif Passaremos a descrever a classe ``MaxHeap`` que é um criadouro de cartolas mágicas. |:tophat:| |:magic_wand:| |:mage_tone4:| A classe ``MaxHeap`` terá os métodos: * ``__init__(self)``: cria uma lista ``self.data`` inicialmente apenas com ``None``; * ``__str__(self)``: retorna uma string usada para exibir um objeto ``MaxHeap``; * ``__len__(self)``: retorna o número de elementos em ``self``; * ``vazio(self)``: retorna ``True`` se ``self`` esta vazio e ``False`` em caso contrário; * ``maxheap(self)``: retorna ``True`` se ``self.data`` é um max-heap; * ``insira(self, item)``: insere ``item`` no ``MaxHeap`` ``self``; * ``construa(self, v)``: insere os elementos de uma lista ``v`` no ``MaxHeap`` ``self`` * ``remove(self)``: remove e retorna o maior elemento do ``MaxHeap`` self. A seguir está uma breve exposição dos métodos na classe junto com alguns exemplos de execução. *Todos os métodos são iguais, mas alguns são mais iguais que o outros!* Devido a sua relevância para a classe ``maxHeap``, o método ``insira()`` e metodo ``remove()`` ganharam cada um a sua própria seção. Essas seções estão mais a frente. A classe ``MaxHeap`` representará um max-heap. O método ``__init__()`` acrescenta uma lista ``data`` com ``None`` ao objeto ``self`` da classe ``MaxHeap``. Os ``n`` elementos de um max-heap serão armazenados em ``self.data[1]``, ``self.data[2]``, ... , ``self.data[n]``. .. code:: python def __init__(self): '''(MaxHeap) -> None CONSTRUTOR da classe MaxHeap. CRIA uma lista self.data com [None] que representa um max-heap vazio. PERIGO. EXCEPCIONALMENTE o elemento na posição de índice zero não faz parte do MaxHeap. O primeiro elemento está na posição de índice 1. ''' self.data = [None] O método ``contrua(self, v)`` insere todos os elementos de ``v`` no ``MaxHeap`` ``self``. O método ``__str__()`` retorna uma string que exibe os elementos que estão no ``MaxHeap``, nível por nível: .. code:: python In [41]: h = MaxHeap() In [42]: v = [1,3,5] In [43]: h.construa(v) In [44]: print(h) 5 1 3 In [45]: h.data Out[45]: [None, 5, 1, 3] In [46]: v Out[46]: [1, 3, 5] In [47]: v = [4,2,6] In [48]: h.construa(v) In [49]: print(h) 6 4 5 1 2 3 In [50]: h.data Out[50]: [None, 6, 4, 5, 1, 2, 3] In [51]: v Out[51]: [4, 2, 6] Veja que ``print(h)`` em ``In [49]`` produz a saída que mostra que: * ``6`` está na raiz; * ``4`` é a filha esquerda de ``6``; * ``5`` é a filha direita de ``6``; * ``1`` é a filha esquerda de ``4``; * ``2`` é a filha direita de ``4``; e * ``3`` é a filha filhe esquerda de ``5``. ``5`` não tem filha direita. O método ``len(self)`` retorna o número de elementos em ``self`` e o método ``vazio()`` retorna ``True`` se ``self`` é um ``MaxHeap`` vazio e retorna ``False`` em caso contrário: .. code:: python In [12]: h = MaxHeap() In [13]: len(h) Out[13]: 0 In [14]: h.insira(7) In [15]: h.insira(3) In [16]: h.insira(9) In [17]: print(h) 9 3 7 In [18]: len(h) Out[18]: 3 In [19]: h = MaxHeap() In [20]: len(h) Out[20]: 0 In [21]: h.vazio() Out[21]: True In [22]: h.insira(7) In [23]: h.insira(3) In [24]: h.insira(9) In [25]: len(h) Out[25]: 3 In [26]: h.vazio() Out[26]: False ``maxheap(self)`` é um método suuupeeer |:woman_superhero_medium_dark_skin_tone:| |:man_superhero_medium_dark_skin_tone:| útil! Esse método retorna ``True`` se ``self.data`` representa um max-heap e retorna ``False`` em caso contrário. Vale a pena examinarmos |:mag_right:| cuidadosamente a implementação desse método já que ele diz muito sobre a estrutura de um max-heap. .. code:: python def maxheap(self): ''' (MaxHeap) -> bool RECEBE um MaxHeap self. RETORNA True se self.data representa um max-heap e False em caso contrário. ''' # apelidos n = len(self.data) dt = self.data # deve ter pelo menos None if n == 0: return False # primeira posição deve ser None if dt[0] != None: return False # verifique se satisfaz a propriedade/invariante de max-heap for filha in range(2, n): mae = filha // 2 # mãe deve ser maior ou igual a filha if dt[mae] < dt[filha]: return False return True Alguns exemplos de execução de ``maxheap()``: .. code:: python In [21]: h = MaxHeap() In [22]: h.maxheap() Out[22]: True In [23]: h.data = [None, 1, 2, 3] In [24]: h.maxheap() Out[24]: False In [25]: h.data = [3, 1, 2] In [26]: h.maxheap() Out[26]: False In [27]: h.data = [None, 3, 1, 2] In [28]: h.maxheap() Out[28]: True No esqueleto de programa a seguir todos os métodos da classe ``MaxHeap`` estão implementados, exceto os métodos ``insira()`` e ``construa()`` que serão deixados como exercício. .. raw:: html Método ``insira()`` ------------------- Para entender como inserir um novo elemento no max-heap talvez valha a pena pegar lápis |:pencil2:| e papel |:notepad_spiral:| e copiar e desenhar |:pencil:| os max-heaps. Suponha que desejamos inserir o valor ``44`` no max-heap da figura abaixo. A inserção na **árvore** se faz criando o nó 13 com o valor 44. Desenhe um nó 13, filho direito do nó 6, com valor 44. A inserção na **lista** se faz através de um mero ``append()`` .. image:: ./imgs/maxheapLista.* :width: 887 :height: 551 :scale: 60 :alt: Representação de uma árvore binária max heap usando lista. :align: center Após a inserção do 44, a árvore deixará de ser max-heap já que a mãe de 44 é 15. Para consertar o max-heap, precisamos fazer o 44 subir até sua posição correta. Para isso, podemos comparar o 44 com seu mãe, 15, no nó 6 da árvore. Nesse caso, como a mãe é menor, o 44 *sobe* para o nó 6 e o 15 *desce* para o nó 13. Desenhe essa troca para sentir o que está acontecendo. Na lista esse sobe-e-desce corresponde a uma *troca* entre os elementos de um par mãe-filha. Agora devemos continuar o processo com a mãe do nó 6, que é o nó 3. Como 17 é menor que 44, o 44 *sobe* novamente e desta vez é o 17 que desce. Mais uma *troca* na lista. A raiz não tem mãe e portanto o processo não deve prosseguir após o 44 chegar na raiz. No caso, o processo continuará comparando 44 com sua mãe 51 e como 51 é maior que 44, o processo termina. Bingo! Em um passe de mágica temos um max-heap. |:magic_wand:| De uma maneira mais curta e grossa... Para inserir um novo elemento no max-heap, devemos inseri-lo no final da lista com um ``append()``. Em seguida, enquanto o valor na mãe desse elemento for menor que ele, o novo elemento deve ser trocado com o valor de sua mãe. O processo continua até o novo elemento encontrar uma mãe que seja maior que ele ou até chegar na raiz. Experimente inserir outros valores, como 8 e 88, para ver se você entendeu o processo. O consumo de tempo desse processo mágico |:magic_wand:| é :math:`\mathtt{\textup{O}(\lg n)}` em que :math:`\mathtt{n}` é o número de elementos no max-heap. Agora implemente o método ``insira()``. No esqueleto há testes que podem ser usados para testar a sua implementação. .. raw:: html 
    def main():
        ''' 
        Unidade de teste da classe MaxHeap 
        '''
        print("Ordenação usando MaxHeap")

        x = [21, 12, 43, 61, 41, 71, 91, 31, 81]
        print(f"Entrada:\n{x}")

        print("\n testes do MaxHeap.insira()")
        h = MaxHeap()
        for item in x:
            h.insira(item)
            print(h)
            input("TECLE enter para continuar ...")

        print("\n teste do construa")
        h = MaxHeap()
        h.construa(x)
        print(h)
Esses testes produzem a seguinte saída. :: Testes ordenação usando MaxHeap Entrada: [21, 12, 43, 61, 41, 71, 91, 31, 81] testes do insira 21 Tecle enter para continuar ... 21 12 Tecle enter para continuar ... 43 12 21 Tecle enter para continuar ... 61 43 21 12 Tecle enter para continuar ... 61 43 21 12 41 Tecle enter para continuar ... 71 43 61 12 41 21 Tecle enter para continuar ... 91 43 71 12 41 21 61 Tecle enter para continuar ... 91 43 71 31 41 21 61 12 Tecle enter para continuar ... 91 81 71 43 41 21 61 12 31 Tecle enter para continuar ... teste do construa 91 81 71 43 41 21 61 12 31 A seguir está uma animação de ``MaxHeap.construa()`` durante o expediente. .. image:: ./imgs/MaxHeap_constroi.* :width: 766 :height: 656 :scale: 50 :alt: Heapsort example :align: center Método ``remova()`` -------------------- Nesta seção explicamos o funcionamento do método ``remova()``. Antes, vale a pena investigarmos |:detective_tone3:| cuidadosamente |:mag_right:| a sua implementação. O começo dela está feito. O caso em que o max-heap está vazio. .. code:: python def remova(self): '''(MaxHeap) -> obj RECEBE um MaxHeap self. REMOVE e RETORNA o maior elemento do MaxHeap. Após remover o maior elemento o MaxHeap é consertado ''' # crie apelidos n = len(self.data) # 1 a mais que o número de itens no MaxHeap dt = self.data # itens: dt[1], dt[2],...,dt[n-1] # MaxHeap vazio: erro if n == 1: print("MaxHeap ERRO: tentativa de remoção em max-heap vazio") return None # MaxHeap tem apenas 1 item if n == 2: return dt.pop() # MaxHeap tem pelo menos dois itens item = dt[1] dt[1] = dt.pop() # arrume MaxHeap n = n-1 mae = 1 # mãe filha = 2 # filha valor = dt[mae] # selecione a maior das duas filhas if filha < n-1 and dt[filha] < dt[filha+1]: filha += 1 while filha < n and valor < dt[filha]: dt[mae] = dt[filha] # elemento da filha sobe mae = filha # mãe desce filha = 2*mae # filha esquerda # selecione a maior das duas filhas if filha < n-1 and dt[filha] < dt[filha+1]: filha += 1 dt[mae] = valor return item Como sempre, alguns exemplos ... .. code:: python In [2]: h = MaxHeap() In [3]: v = [1, 4, 5, 3, 6] In [4]: h.construa(v) In [5]: v Out[5]: [1, 4, 5, 3, 6] In [6]: h.data Out[6]: [None, 6, 5, 4, 1, 3] In [7]: h.remova() Out[7]: 6 In [8]: h.data Out[8]: [None, 5, 3, 4, 1] In [9]: h.remova() Out[9]: 5 In [10]: h.data Out[10]: [None, 4, 3, 1] In [11]: h.remova() Out[11]: 4 In [12]: h.data Out[12]: [None, 3, 1] In [13]: h.remova() Out[13]: 3 In [14]: h.data Out[14]: [None, 1] In [15]: h.remova() Out[15]: 1 In [16]: h.data Out[16]: [None] In [17]: h.remova() MaxHeap ERRO: tentativa de remoção em max-heap vazio |:face_with_monocle:| Contemple o max-heap abaixo. Suponha que ``h`` é o nome deste max-heap e ``h.data`` é o nome da lista que mantém seus itens. Na ilustração o valor ``None`` da posição ``h.data[0]`` não está sendo mostrado. .. image:: ./imgs/maxheapLista.* :width: 887 :height: 551 :scale: 60 :alt: Max heap em uma lista :align: center O maior item de ``h`` está sempre na posição ``data[1]``. No exemplo esse valor é 51. Assim o valor que ``h.remova()`` deve **retornar** é 51. Até ai *não há nada novo sob o Sol*. Para **removermos** 51 simplesmente copiamos o último valor de ``h.data`` antes de apagá-lo obtendo assim a lista .. raw:: html 
    +----+----+----+----+----+----+----+----+----+----+----+
        | 12 | 46 | 17 | 34 | 41 | 15 | 14 | 23 | 30 | 21 | 10 |
        +----+----+----+----+----+----+----+----+----+----+----+
           1    2    3    4    5    6    7    8    9   10   11
Bem, o problema agora é que essa coisa não é mais um max-heap... Antes de irmos embora precisamos fazer uma faxina para que ``h.data`` volte a ser o bom e velho max-heap que já foi um dia. Vocês lembram, né?! Os filhos e filhas de uma nó ``i`` são os nós ``2*i`` e ``2*i+1``. A propriedade básica, também chamada de **invariante**, que um max-heap deve satisfazer é que **Propriedade de uma max-heap**: Mães e pais devem ser maiores ou iguais a suas filhas e filhos. Por exemplo, as filhas do nó 5 estão nos nós 10 e 11 e com essa família está tudo bem já que :math:`\mathtt{41 \geq 21}` e :math:`\mathtt{41 \geq 10}`. Voltando, como o valor 12 no nó 1 não é maior ou igual que os valores sentados nos nós 2 e 3, que são 46 e 17, então não temos um max-heap. A ideia agora é meio andar na contramão do como vocês fizeram no método ``insira()``. Em `insira()` vocês colocavam um novo item no final e subiam até que ele fosse menor que seu pai ou mãe ou chegasse no nó 1, no caso de ser o maior valor no max-heap. Para encontrarmos uma família que aceita o 12 vamos descendo com ele até que seja maior ou igual a suas filhas e filhos ou não tenha filhas ou filhos. Vejamos as configurações da lista durante as iterações deste processo. .. raw:: html 
     12 desce e 46 sobe
         
        +----+----+----+----+----+----+----+----+----+----+----+
        | 46 | 12 | 17 | 34 | 41 | 15 | 14 | 23 | 30 | 21 | 10 |
        +----+----+----+----+----+----+----+----+----+----+----+
           1    2    3    4    5    6    7    8    9   10   11

         12 desce e 41 sobe
         
        +----+----+----+----+----+----+----+----+----+----+----+
        | 46 | 41 | 17 | 34 | 12 | 15 | 14 | 23 | 30 | 21 | 10 |
        +----+----+----+----+----+----+----+----+----+----+----+
           1    2    3    4    5    6    7    8    9   10   11

         12 desce e 21 sobe
         
        +----+----+----+----+----+----+----+----+----+----+----+
        | 46 | 41 | 17 | 34 | 21 | 15 | 14 | 23 | 30 | 12 | 10 |
        +----+----+----+----+----+----+----+----+----+----+----+
           1    2    3    4    5    6    7    8    9   10   11
Chegamos em um max-heap! O valor 12 no nó 10 não tem filhos ou filhas para reclamar dele. Se aplicarmos novamente ``h.remove()`` o valor a ser retornado seria 46, o valor no nó 1 e obteríamos a seguinte sequência de estados da lista ``h.data`` ao logo da faxina. .. raw:: html 
     10 vai para o nó 1 e o nó 11 é apagado
         
        +----+----+----+----+----+----+----+----+----+----+
        | 10 | 12 | 17 | 34 | 41 | 15 | 14 | 23 | 30 | 21 |
        +----+----+----+----+----+----+----+----+----+----+
           1    2    3    4    5    6    7    8    9   10  

         10 desce e 41 sobe
         
        +----+----+----+----+----+----+----+----+----+----+
        | 41 | 10 | 17 | 34 | 12 | 15 | 14 | 23 | 30 | 21 |
        +----+----+----+----+----+----+----+----+----+----+
           1    2    3    4    5    6    7    8    9   10  

         10 desce e 34 sobe
         
        +----+----+----+----+----+----+----+----+----+----+
        | 41 | 34 | 17 | 10 | 21 | 15 | 14 | 23 | 30 | 12 |
        +----+----+----+----+----+----+----+----+----+----+
           1    2    3    4    5    6    7    8    9   10

         10 desce e 30 sobe
         
        +----+----+----+----+----+----+----+----+----+----+
        | 41 | 34 | 17 | 30 | 21 | 15 | 14 | 23 | 10 | 12 |
        +----+----+----+----+----+----+----+----+----+----+
           1    2    3    4    5    6    7    8    9   10
Max-heap! Por acaso paramos novamente quando o item que estava descendo a ladeira, o valor 10, chegou em um nó que não tem filhos ou filhas. Isso foi uma coincidência! Poderíamos ter parado no meio da descida, bastava que 10 fosse maior ou igual a seus ... Experimentos ------------ Depois de implementarmos a nossa classe ``MaxHeap``, deixemos as funções trabalharem em paz e apreciemos atentamente a paisagem. Aqui estão os resultados de alguns experimentos obtidos ordenando-se listas aleatórias com o algoritmo de: * ordenação por inserção: ``insercao()``; * ordenação por inserção binária (presente na classe ``DicioB``): ``insercaoB()``; * ordenação por intercalação, versão recursiva: ``mergeR()``; * ordenação por intercalação, versão iterativa: ``mergeI()``; * ordenação por separação, versão recursiva: ``quick()``; * ordenação por seleção: ``selecao()``; * ordenação por seleção: ``heapsort()`` que usa sua classe ``MaxHeap``; e * ``list.sort()`` que é o método nativo de ordenação de objetos da classe ``list``. Os tempos estão em segundos. :: n insercao insercaoB mergeR mergeI quick selecao heapsort sort 256 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 512 0.01 0.00 0.00 0.00 0.00 0.01 0.00 0.00 1024 0.03 0.02 0.00 0.00 0.00 0.04 0.00 0.00 2048 0.14 0.08 0.00 0.00 0.00 0.13 0.01 0.00 4096 0.57 0.30 0.01 0.01 0.01 0.52 0.01 0.00 8192 2.35 1.34 0.02 0.02 0.02 2.06 0.03 0.00 16384 9.66 5.45 0.04 0.04 0.04 8.42 0.07 0.00 32768 37.90 21.44 0.09 0.09 0.08 36.75 0.14 0.01 65536 158.37 90.79 0.20 0.19 0.17 167.16 0.32 0.01 131072 658.00 385.78 0.40 0.39 0.35 985.65 0.72 0.03 Os resultados experimentais mostram o comportamento quadrático da função ``selecao()``. O tempo gasto por ``selecao()`` aproximadamente **quadruplica** a medida que o número de elementos da lista **dobra**. É impressionante como a filha da ``selecao()``, a função ``heapsort()``, é muito mais rápida que sua mãe. Tudo isso graças a maneira que os dados são organizados, graças aos objetos da classe ``MaxHeap`` que são a nossa cartola |:tophat:| mágica |:magic_wand:|. Ainda assim, a ``list.sort()`` do Python gasta muito menos tempo que nossas funções. Isso nos diz que se desejarmos ordenar listas devemos sempre preferir as funções nativas. A propósito, isso é verdade em geral! Na prática, longe do escopo do estudo de algoritmos dessa disciplina, devemos preferir funções e classes nativas da linguagem que estivermos utilizando a criar nossas soluções caseiras. Afinal, funções nativas foram extensivamente testadas e otimizadas. Apesar de que o tempo gasto por ``list.sort()`` ser muito menor que os das demais funções, se nossa tabela acima fosse um pouco maior notaríamos que o seu consumo de tempo assintótico é também :math:\mathtt{\textup{O}(n \lg n)}`. Heapsort e espaço extra ------------------------ A animação a seguir mostra o Heapsort trabalhando. A construção do max-heap termina quando as barras ficam todas pintadas de azul claro. Em seguida vem a fase iterativa em que, a cada iteração, um elemento é removido do max-heap. .. image:: ./imgs/heapsortl.* :width: 766 :height: 656 :scale: 50 :alt: Heapsort :align: center Ordenações que são feitas em espaço extra constante recebem em inglês o adjetivo *in-place*, que é sexy, ou o adjetivo em latin de *in situ*, que é mais sexy ainda! Independentemente do adjetivo, todos significam a mesma coisa, todo o trabalho é feito utilizando apenas a própria lista e algumas poucas variáveis para administrar o serviço. Propagandeamos uma função ``heapsort()`` de consumo de tempo :math:`\mathtt{\textup{O}(n\ \lg\ n)}` e espaço extra constante, em que ``n`` é o número de elementos na lista a ser ordenada. Essa propaganda foi enganosa... A função ``heapsort()`` que entregamos consome tempo :math:`\mathtt{\textup{O}(n \lg n)}` como prometido. Entretendo, o espaço... o espaço... o espaço adicional temporariamente usado para rascunho é proporcional é :math:`\mathtt{n}`, e não constante como dizia a propaganda. Esse espaço é aquele usado pela objeto ``h`` da classe ``MaxHeap``. Como somos habituados e muito bem treinados a dar desculpas... em nossa defesa... ao público consumidor... temos a dizer que realmente poderíamos ter entregue um ``heapsort()`` como prometido. Então qual foi a razão de não termos feito isso? Bem, entregar o prometido daria um pouco mais de trabalho, não muito, mas o orçamento que tínhamos reservado não cobriria as despesas. Teríamos que trabalhar mais *cirurgicamente* com índices como argumentos de métodos e funções e mais algumas coisinhas. Assim, fica para outra vez... Aquelas e aqueles interessados podem dar uma olhada na página `Heapsort `_ de Paulo Feofiloff. Lições ------ |:woman_raising_hand_dark_skin_tone:| Antes de mais nada, a classe ``MaxHeap`` que desenvolvemos é uma espécie de *versão caseira* e *simplificada* do módulo `heapq `_ da linguagem Python. A utilidade de *heaps* no seus sabores **max** e **min** vai muito, muito mesmo, além de ordenação. Heaps são uma das estruturas usadas em projetos de **filas priorizadas** ou `Priority Queues `_. Veja um pouco mais sobre aplicações e aspectos da implementação de *heaps* na `página da documentação `_ do módulo ``heapq`` da Linguagem Python. No que diz respeito ao ``heapsort()``, notem o **pré-processamento**. Em um primeiro momento a função não está se preocupando com a ordenação. A sua única preocupação é construir um max-heap. Depois, com um max-heap em mãos, a função *voa baixo* selecionando o maior item e restaurando o max-heap. Finalmente, implementar o Heapsort nos deu um gostinho de quanto a organização dos dados influencia a eficiência de programas. No nosso caso, usamos ``MaxHeap`` para turbinar, dar um *booster* (termo bem atual!), na ordenação por seleção. Aquelas e aqueles interessados em mais detalhes podem dar uma olhada na página `Heapsort `_ de Paulo Feofiloff. .. image:: ./imgs/heapsortr.* :width: 766 :height: 656 :scale: 50 :alt: Heapsort :align: center Em termos de programação, em geral, devemos preferir utilizar funções nativas a criarmos nossas próprias soluções caseiras. Já vimos esse fenômeno comparando os tempos gastos pelas nossas implementações de dicionários com o tempo gasto pelos dicionários nativos do Python, objetos da class ``dict``. Vimos o mesmo comportamento entre os nossos ``Array2D`` e as classes do NumPy. .. raw:: html Exercícios ---------- #. Suponha que ``h`` é um objeto da classe ``MaxHeap``. Quais listas a seguir são legítimas representações para um max-heap da classe ``MaxHeap``? * ``h.data=[None, 1, 2, 3]`` * ``h.data=[None, 3, 2, 1]`` * ``h.data=[None, 3, 1, 2]`` * ``h.data=[None, 15, 2, 1, 14]`` * ``h.data=[None]`` * ``h.data=[]`` #. Escreva o método ``insira()`` da classe ``MaxHeap``. #. Suponha que ``h`` é um ``MaxHeap``. Qual o número de comparações **entre elementos de** ``h`` que são feitas por ``h.insira(item)`` se * ``h.data=[None, 15, 5, 11, 4, 3]`` e ``item = 10``? * ``h.data=[None, 15, 5, 11, 4, 3, 10]`` e ``item = 16``? * ``h.data=[None, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]`` e ``item = 11``? #. Em geral, se um ``MaxHeap`` ``h`` tem ``n`` itens, aproximadamente quantas comparações **entre elementos da lista** ``h.data`` são feitas por ``h.insira(item)`` no **melhor caso** e no **pior caso**? #. Em notação assintótica, qual o consumo de tempo do seu método ``insira()`` da classe ``MaxHeap`` no **melhor caso**? E no **pior caso**? #. Escreva o método ``construa()`` da classe ``MaxHeap``. #. Suponha que ``h`` é um ``MaxHeap`` vazio e ``v`` é uma lista com ``n`` elementos. Em notação assintótica, qual o consumo de tempo do seu método ``construa()`` no **melhor caso**? E no **pior caso**? #. Escreva sua própria implementação do método ``remova()`` da classe ``MaxHeap``. #. Suponha que ``h`` é um ``MaxHeap`` com ``n`` elementos. Em notação assintótica, qual o consumo de tempo do seu método ``remova()`` no **melhor caso**? E no **pior caso**? #. Faça experimentos com as funções implementadas, ``insercao()``, ``mergesort()``, ``quicksort()`` e ``heapsort()`` e, baseando-se nesses exeperimentos, refita sobre qual função tem o melhor desempenho para listas: * aleatórias? * crescentes ou quase crescentes? * decrescentes ou quase decrescentes? #. Os tempos obtidos nos experimentos comprovam a suas conclusões sobre o consumo de tempo dos métodos ``insira()`` e ``remova()`` da classe ``MaxHeap``? Por quê? Para saber mais --------------- * `Heapsort `_ de `Projeto de Algoritmos `_ de Paulo Feofiloff. * `Filas priorizadas `_ por Paulo Feofiloff. * `Priority Queues `_ do livro `Algorithms `_ de Robert Sedgewick e Kevin Wayne. * `heapq — Heap queue algorithm `_ da `Python documentation `_ . * `queue `_ da `Python documentation `_ . * `Sorting HOW TO `_ da `Python documentation `_.