Questão 66980

Um professor de Algoritmos e Estruturas de Dados está ensinando sobre a estrutura de dados 'Fila de Prioridade' (Priority Queue) e sua implementação mais comum, o 'Heap Binário'. Ele quer que os alunos entendam por que um Heap é uma estrutura mais eficiente para implementar uma fila de prioridade do que uma simples lista ou array. Para isso, ele apresenta o cenário de um sistema de gerenciamento de processos em um hospital, onde os pacientes são atendidos não por ordem de chegada, mas pela gravidade de sua condição. Ele cita um trecho de um livro sobre o tema: "Uma Fila de Prioridade é uma estrutura de dados abstrata que armazena elementos com uma prioridade associada e permite duas operações principais: `inserir(elemento, prioridade)` e `extrair_max()` (ou `extrair_min()`), que remove e retorna o elemento com a maior (ou menor) prioridade. Se usarmos um array não ordenado, a inserção é $O(1)$, mas a extração do máximo requer uma busca por todo o array, custando $O(n)$. Se usarmos um array ordenado, a extração é $O(1)$, mas a inserção requer o deslocamento de elementos, custando $O(n)$. Um Heap Binário, que é uma árvore binária quase completa com a propriedade do heap (o pai é sempre maior/menor que os filhos), oferece um compromisso melhor: tanto a inserção quanto a extração do máximo podem ser feitas em tempo $O(\log n)$." O professor então desenha um Max-Heap (onde o pai é sempre maior que os filhos) e pede aos alunos para simularem a inserção de um novo paciente de alta prioridade.

Dado o seguinte Max-Heap, representado como um array `[100, 80, 90, 60, 70, 50, 40]`, como a operação de `inserir(95)` seria realizada?