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 \(\mathtt{\textup{O}(n \lg n)}\) em que \(\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 \(\mathtt{n}\), é o chamado espaço extra \(\mathtt{\textup{O}(n)}\).

Apesar da modéstia no nome, o Quicksort, no pior caso consome tempo \(\mathtt{\textup{O}(n^2)}\) e usa espaço extra \(\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 é \(\mathtt{\textup{O}(n \lg n)}\) e espaço extra pode ser limitado por \(\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. 🤨 Criaremos uma classe que organiza os elementos de uma lista de uma tal forma que permitirá que projetemos uma função que consome tempo \(\mathtt{\textup{O}(n \lg n)}\) e espaço extra \(\mathtt{\textup{O}(1)}\) (!) para ordenar uma lista com \(\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).

🤔 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 \(\mathtt{v[0{:}n]}\) é crescente se

\[\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.

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.

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 é \(\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.

    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] \(\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 \(\mathtt{\leq}\) val2.

No início da última iteração temos que \(\mathtt{i = 1}\) e portanto v[1:n] é crescente e v[0] \(\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 \(\mathtt{\textup{O}(i)}\).

\[\begin{split}\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}\end{split}\]

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() é \(\mathtt{\textup{O}(n^2)}\) em que \(\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 👀 como magicamente 🧙🏽 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 🪄 logarítmico, \(\mathtt{\textup{O}(\lg n)}\). em vez de linear, \(\mathtt{\textup{O}(n)}\). Com isso, como o algoritmo faz \(\mathtt{n}\) iterações, chegaremos a mais um algoritmo de consumo de tempo \(\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 \(\mathtt{\textup{O}(n \lg n})\) mesmo antes de revelar como a maga 🧙🏿 fará a sua mágica. 🪄 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.

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().

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 🎩 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 🎩 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 \(\mathtt{\textup{O}(\lg n)}\), em que \(\mathtt{n}\) é o número de elementos de v. Com isso, concluímos que o consumo de tempo total da linhas 2 e 3 é \(\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 \(\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 \(\mathtt{n}\) elementos que foram inseridos, o consumo de tempo total das linhas 3 e 4 será, também, \(\mathtt{\textup{O}(n \lg n})\).

Com isso chegamos a seguinte conclusão:

Conclusão. O consumo de tempo da função heapsort() é \(\mathtt{\textup{O}(n \lg n)}\) em que \(\mathtt{n}\) é o número de elementos na lista.

A única coisa que resta a fazer é revelar como a maga 🧙🏾 utiliza a cartola para fazer a mágica. 🪄 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? 🤦‍♂️

Heaps

Nesta seção desvendaremos os segredos da cartola. 🎩 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?

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.

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?! 🤔 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 \(\mathtt{k}\) de uma árvore binária possui no máximo \(\mathtt{2^k}\) nós. O nível 0 tem um \(\mathtt{2^0=1}\) nó que é a raiz da árvore, o nível 1 tem até \(\mathtt{2^1=2}\) nós, o nível 2 tem até \(\mathtt{2^2=4}\) nós, o nível 3 tem até \(\mathtt{2^3=8}\) nós, etc. No nosso caso, para que a nossa cartola 🎩 seja mágica, apenas o último nível da árvore não precisa estar completo, pode ter menos que \(\mathtt{2^k}\) nós. No exemplo o último é o nivel 3 que tem \(\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 👀 uma árvore.

Primeiro consideraremos que o elemento do nó \(\mathtt{i}\) está na posição de índice \(\mathtt{i}\) da lista. As relações familiares de um nó \(\mathtt{i}\) são obtidas através de multiplicações e divisões por 2:

• a mãe de \(\mathtt{i}\) é o nó \(\mathtt{i//2}\) e

• as filhas são o nó \(\mathtt{2*i}\) e o nó \(\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.

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

Passaremos a descrever a classe MaxHeap que é um criadouro de cartolas mágicas. 🎩 🪄 🧙🏾 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].

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:

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:

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 🦸🏾‍♀️ 🦸🏾‍♂️ útil! Esse método retorna True se self.data representa um max-heap e retorna False em caso contrário. Vale a pena examinarmos 🔎 cuidadosamente a implementação desse método já que ele diz muito sobre a estrutura de um max-heap.

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():

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.

Método insira()

Para entender como inserir um novo elemento no max-heap talvez valha a pena pegar lápis ✏️ e papel 🗒️ e copiar e desenhar 📝 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()

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. 🪄

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 🪄 é \(\mathtt{\textup{O}(\lg n)}\) em que \(\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.

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.

Método remova()

Nesta seção explicamos o funcionamento do método remova(). Antes, vale a pena investigarmos 🕵🏽 cuidadosamente 🔎 a sua implementação. O começo dela está feito. O caso em que o max-heap está vazio.

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 …

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

🧐 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.

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

    +----+----+----+----+----+----+----+----+----+----+----+
    | 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 \(\mathtt{41 \geq 21}\) e \(\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.

     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.

     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 🎩 mágica 🪄.

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.

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 \(\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 \(\mathtt{\textup{O}(n \lg n)}\) como prometido. Entretendo, o espaço… o espaço… o espaço adicional temporariamente usado para rascunho é proporcional é \(\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

🙋🏿‍♀️ 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.

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.

Exercícios

1. 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=[]

2. Escreva o método insira() da classe MaxHeap.

3. 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?

4. 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?

5. 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?

6. Escreva o método construa() da classe MaxHeap.

7. 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?

8. Escreva sua própria implementação do método remova() da classe MaxHeap.

9. 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?

10. 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?

11. 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.