Compartilhamento de tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

amontoar

Heap e fila de prioridade:

A fila de prioridade é um tipo de dados abstrato e o heap é uma estrutura de dados, portanto, o heap não é uma fila de prioridade. O heap é uma forma de implementar uma fila de prioridade.
Existem muitas maneiras de implementar filas prioritárias, como matrizes e listas vinculadas. No entanto, essas implementações só podem garantir que uma das operações de inserção e exclusão possa ser concluída em complexidade de tempo O(1)O(1), enquanto a outra operação precisa ser concluída em O(N)O(N) Concluída dentro do complexidade do tempo. O heap pode permitir que a operação de inserção da fila de prioridade seja concluída dentro da complexidade de tempo de O(log N)O(logN) e a operação de exclusão seja concluída dentro da complexidade de tempo de O(log N)O(logN) .

Um heap é uma árvore binária especial que atende às seguintes condições:

1. Árvore binária completa (os nós são colocados em ordem da esquerda para a direita);
2. O valor de cada nó deve ser maior ou igual ou menor ou igual ao valor de seu nó filho.

Recursos da pilha:

1. Os elementos podem ser inseridos no heap em complexidade de tempo O (logN);
2. Os elementos podem ser excluídos do heap em complexidade de tempo O (logN);
3. O valor máximo ou mínimo no heap pode ser obtido dentro da complexidade de tempo O(1).

Classificação de pilha:

Heap máximo: o valor de cada nó no heap é maior ou igual ao valor de seu nó filho. O elemento superior (nó raiz) do heap máximo é o valor máximo no heap.
Heap mínimo: O valor de cada nó no heap é menor ou igual ao valor de seu nó filho. O elemento superior (nó raiz) de um heap mínimo é o valor mínimo no heap.
O número do nó atual é i, o número do filho esquerdo é 2i e o número do filho direito é 2i+1.

Complexidade do tempo e complexidade do espaço

Classificação de pilha

Teoria: Heap sort refere-se ao uso da estrutura de dados do heap para classificar um conjunto de elementos não ordenados.

As etapas do algoritmo de classificação min-heap são as seguintes:

Amontoe todos os elementos em uma pilha mínima;
Retire e exclua o elemento superior do heap e coloque o elemento superior do heap no conjunto de dados T que armazena os elementos ordenados;
Neste momento, o heap será ajustado ao novo heap mínimo;
Repita as etapas 3 e 4 até que não haja mais elementos no heap;
Neste ponto, obtém-se um novo conjunto de dados T, no qual os elementos são organizados do menor para o maior.

As etapas do algoritmo de classificação máxima de heap são as seguintes:

Empilhe todos os elementos em um heap máximo;
Retire e exclua o elemento superior do heap e coloque o elemento superior do heap no conjunto de dados T que armazena os elementos ordenados;
Neste momento, o heap será ajustado ao novo heap máximo;
Repita as etapas 3 e 4 até que não haja mais elementos no heap;
Neste ponto, obtém-se um novo conjunto de dados T, no qual os elementos são organizados do maior para o menor.
Complexidade de tempo: O(Nlog N). N é o número de elementos no heap.

Complexidade do espaço: O(N). N é o número de elementos no heap.