Questões de Concurso sobre Heapsort (max heap)

A Secretaria de Saúde de determinado município desenvolveu um sistema para organizar a fila de pacientes em uma unidade de pronto atendimento. O sistema precisa ordenar os registros com base na prioridade de atendimento (alta, média ou baixa) e, dentro de cada nível de prioridade, ordenar os pacientes de acordo com a data e hora de chegada. Durante os testes do sistema, a equipe de TI implementou diferentes algoritmos de ordenação, analisando suas características e desempenho.

Cada um desses algoritmos foi descrito pelos programadores da seguinte forma:

• Implementação 1: o algoritmo percorre repetidamente a lista, comparando e trocando elementos adjacentes até que toda a lista esteja ordenada.

• Implementação 2: a lista é dividida em duas metades recursivamente, e as metades ordenadas são combinadas para formar a lista final.

• Implementação 3: o algoritmo constrói a lista ordenada elemento por elemento, inserindo cada novo item na posição correta.

• Implementação 4: uma estrutura de heap é utilizada para armazenar os elementos, garantindo que o maior ou menor elemento seja extraído de forma eficiente.

Com base nas descrições anteriores, assinale a alternativa que relaciona corretamente as implementações aos algoritmos de ordenação.

O que é uma tabela Heap?

Heaps são estruturas de dados que permitem operações eficientes de inserção, remoção e acesso; seu uso pode melhorar significativamente a eficiência de algoritmos de ordenação.

Um analista tem disponíveis quatro algoritmos de ordenação: inserção, mergesort, heapsort e bubblesort. Como o analista não tem conhecimento sobre o tamanho do conjunto de dados e as suas condições de ordenação inicial, resolve utilizar como critério de escolha a menor complexidade do pior caso.

Considerando-se esse critério de menor complexidade do pior caso, quais seriam os dois algoritmos que o analista deve utilizar para fazer uma primeira seleção?

Medir a complexidade dos métodos de ordenação é fundamental para entender o desempenho desses algoritmos e poder fazer escolhas adequadas dependendo do contexto do problema. Qual método de ordenação o pior caso tem a mesma complexidade do método Quick Sort no pior caso?

Sobre estrutura de dados e algoritmos, analise as opções a seguir e assinale a INCORRETA:

Considere o código a seguir:

public class HeapSort {

public void heapSort(int arr[]) {

int n = arr.length;

for (int i = n / 2 - 1; i >= 0; i--) {

heapify(arr, n, i);

}

for (int i = n - 1; i > 0; i--) {

int temp = arr[0];

arr[0] = arr[i];

arr[i] = temp;

heapify(arr, i, 0);

}

}

void heapify(int arr[], int n, int i) {

int maior = i;

int esquerda = 2 * i + 1;

int direita = 2 * i + 2;

if (esquerda < n && arr[esquerda] > arr[maior]) {

maior = esquerda;

}

if (direita < n && arr[direita] > arr[maior]) {

maior = direita;

}

if (maior != i) {

int temp = arr[i];

arr[i] = arr[maior];

arr[maior] = temp;

heapify(arr, n, maior);

}

}

public static void main(String args[]) {

int arr[] = {12, 11, 13, 5, 6, 7};

int n = arr.length;

HeapSort heapSort = new HeapSort();

heapSort.heapSort(arr);

System.out.println("Array ordenado: ");

for (int i : arr) {

System.out.print(i + " ");

}

}

}

Considerando o algoritmo apresentado, qual é a principal característica deste algoritmo de ordenação?

Heapsort é um algoritmo de ordenação baseado na estrutura de dados heap. Sobre as características desse algoritmo de ordenação, assinale, a afirmativa correta.

O algoritmo Heapsort é um algoritmo de ordenação eficiente que utiliza uma estrutura de dados chamada heap para ordenar os elementos. Como exemplo, um sistema de monitoramento de rede pode usar Heapsort para ordenar logs de eventos de rede por timestamp, permitindo a análise cronológica dos eventos de rede. Escolha qual das seguintes afirmações é verdadeira sobre a complexidade do Heapsort e seu comportamento na prática.

A complexidade de algoritmos refere-se à análise e à avaliação de desempenho de um algoritmo no que se diz respeito aos recursos computacionais necessários para se resolver determinado problema. O tempo de execução do algoritmo Heapsort é

O tempo de execução do Heapsort é o O(n²), portanto mais rápido que o Quicksort.

As alternativas a seguir apresentam características dos arquivos Heap, à exceção de uma. Assinale‐a.