Imprime os maiores elementos K em um determinado heap em O (K * log (K))?

Dado o seguinte problema, não estou completamente certo com a minha solução atual:

Pergunta:

Dado um heap máximo com n elementos, que é armazenado em um array A , é possível imprimir todos os maiores elementos K em O(K*log(K)) ?

Minha resposta :

Sim, é, já que pesquisar um elemento requer O(log(K)) , portanto, fazer isso

para elementos O(K * log(K)) o tempo de execução seria O(K * log(K)) .

Isso é possível em um heap máximo porque você está imprimindo apenas elementos da tree, não os extraindo.

Comece identificando o elemento máximo, localizado no nó raiz. Forme um ponteiro para um nó e inclua-o em uma lista “máxima” de outra forma vazia. Então, para cada um dos valores de k , execute os seguintes passos em um loop.

  • Pop o elemento máximo da lista, tendo O (1).
  • Imprima seu valor, tomando O (1).
  • Insira cada um dos filhos desse elemento máximo na lista. Mantenha a ordenação ao inseri-los, tomando o tempo O (log (tamanho da lista)). O tamanho máximo desta lista, já que estamos executando este loop k vezes, é tamanho de ramificação * k. Portanto, esta etapa leva o tempo O (log (k)).

No total, então, o tempo de execução é O (klog (k)), conforme desejado.

Procurando por um elemento em um heap de tamanho N não é O (K). Primeiro, não faz sentido que a complexidade de tempo para encontrar um elemento dependa do número de elementos que você está tentando extrair (que é o que K representa). Além disso, não existe uma pesquisa em um heap – a menos que você conte a busca padrão de todos os elementos em O (N).

No entanto, encontrar o maior elemento em um heap é O (1) por design (obviamente estou assumindo que ele é um heap máximo, portanto, o elemento máximo está no topo do heap) e removendo o maior elemento de um heap de O tamanho N é O (log (N)) (substitua-o por um elemento leaf e faça com que a folha percorra a pilha novamente).

Portanto, extrair elementos K de um heap e retornar o heap de elementos não extraídos levaria o tempo O (K · log (N)).

O que acontece se você extrair K elementos não destrutivos do heap? Você pode fazer isso mantendo um monte de heaps (onde o valor de um heap é o valor do seu elemento máximo). Inicialmente, esse monte de heaps contém apenas um elemento (o heap original). Para extrair o próximo elemento máximo, você extrai o heap superior, extrai seu elemento superior (que é o máximo) e, em seguida, reinsira os dois sub-heaps de volta nos heap-of-heaps.

Isso aumenta o montão de heaps em um em cada remoção (remove um, adiciona dois), o que significa que ele nunca irá conter mais do que K elementos , e então o remove-one-add-two levará O (log (K)) ). Iterar isso e você obtém um algoritmo O (K · log (K)) real que retorna os elementos K superiores, mas não pode retornar o heap de elementos não extraídos.

Eu achei as outras respostas confusas, então decidi explicá-las com um exemplo real. Suponha que o heap original é tamanho N e você deseja encontrar os k maiores elementos. Essa solução usa o tempo O (klogk) e o espaço O (k).

  10 / \ 5 3 / \ /\ 4 1 2 0 Original Heap, N = 7 

Quer encontrar o quinto maior elemento. k = 5 Nota: No novo heap, você precisa armazenar o ponteiro no heap original. Isso significa que você não remove ou altera o heap original. O heap original é somente leitura. Portanto, você nunca precisa fazer nenhuma operação que requeira tempo O (logN).

Seja x o ponteiro para o valor x no heap original.

1ª Iteração: Coloque o ponteiro do nó raiz no novo heap

Etapa 1: adicionar ponteiro ao nó 10

  10' New Heap, size = 1, root = 10', root->left = 5, root right->3 

Imprima o 1º maior elemento = 10

2ª iteração: Consulte o heap original e insira ambos os filhos no novo heap. (Armazenando os pointers para eles e não o valor em si). O motivo pelo qual você deseja armazenar o ponteiro é para que você possa acessá-los em O (1) a partir do heap original posteriormente para procurar seus filhos em vez de O (N) para procurar onde esse valor está localizado no heap original.

Etapa 2a: Procure o filho à esquerda do nó raiz do novo heap do heap original. Adicione um ponteiro para o filho esquerdo (nesse caso, 5 ‘) para o novo heap.

  10' / 5' New Heap, size = 2, root = 10', root->left = 5, root right->3 

Etapa 2b: Procure o filho direito do nó raiz do novo heap do heap original. Adicione um ponteiro para o filho esquerdo (nesse caso, 3 ‘) para o novo heap.

  10' / \ 5' 3' New Heap, size = 3, root = 10', root->left = 5, root right->3 

Etapa 2c: Remover o nó raiz de New Heap. (Swap max node com right most leave, remove o nó raiz e faz borbulhar a raiz atual para manter a propriedade heap)

  10' swap 3' remove & bubble 5' / \ => / \ => / 5' 3' 5' 10' 3' New Heap, size = 2, root = 5', root->left = 4, root right->1 

Imprima o segundo maior elemento = 5

Etapa 3a: Procure o filho à esquerda do nó raiz do novo heap do heap original. Adicione um ponteiro para o filho esquerdo (nesse caso, 4 ‘) para o novo heap.

  5' / \ 3' 4' New Heap, size = 3, root = 5', root->left = 4, root right->1 

Etapa 3b: Procure o filho direito do nó raiz do novo heap do heap original. Adicione um ponteiro para o filho esquerdo (neste caso, 1 ‘) para o novo heap.

  5' / \ 3' 4' / 1' New Heap, size = 4, root = 5', root->left = 4, root right->1 

Etapa 3c: Remover o nó raiz do New Heap. (O nó Swap max (5 ‘) de New Heap, com sua parte mais à direita, sai do heap original (1’) do New Heap, remove o nó raiz e faz borbulhar a raiz atual para manter a propriedade heap)

  5' Swap 1' remove & bubble 4' / \ => / \ => / \ 3' 4' 3' 4' 3' 1' / / 1' 5' New Heap, size = 3, root = 4', root->left = NULL, root right->NULL 

Imprimir o terceiro maior elemento = 4

A etapa 4a e a etapa 4b não fazem nada, já que o nó raiz não tem nenhum filho, neste caso, da pilha original.

Etapa 4c: Remover o nó raiz do New Heap. (O nó Swap max com o máximo de left, remove o nó raiz e faz borbulhar a raiz atual para manter a propriedade heap em New Heap)

  4' Swap 1' remove & bubble 3' / \ => / \ => / 3' 1' 3' 4' 1' New Heap, size = 2, root = 3', root->left = 2, root right->0 

Imprima o 4º maior elemento = 3

Etapa 5a: Procure o filho à esquerda do nó raiz do novo heap do heap original. Adicione um ponteiro para o filho esquerdo (neste caso, 2 ‘) para o novo heap.

  3' / \ 1' 2' New Heap, size = 3, root = 3', root->left = 2, root right->0 

Etapa 5b: Procure o filho direito do nó raiz do novo heap do heap original. Adicione um ponteiro para o filho esquerdo (neste caso, 0 ‘) para o novo heap.

  3' / \ 1' 2' / 0' New Heap, size = 4, root = 3', root->left = 2, root right->0 

Etapa 5c: Remova o nó raiz do New Heap. (Swap max node (3 ‘) com sua parte mais à direita do heap original (que é 0’) no New Heap, remova o nó raiz e faça borbulhar a raiz atual para manter a propriedade heap em New Heap)

  3' Swap 0' Remove & Bubble 2' / \ => / \ => / \ 1' 2' 1' 2' 1' 0' / / 0' 3' New Heap, size = 3, root = 2', root->left = NULL, root->right = NULL 

Imprima o quinto maior elemento = 2

Finalmente, já que passamos por k iterações, k = 5. Agora podemos extrair o valor do elemento raiz do novo heap. Nesse caso, o valor é 2. Portanto, encontramos o k maior valor do heap original.

Complexidade do Tempo, T (N, k) = O (klogk) Complexidade do Espaço, S (N, k) = O (k)

Espero que isto ajude!

Logo Chee Loong,

Universidade de Toronto.

De fato, é muito fácil, extrair o elemento max é O(log(N)) onde N é o tamanho do heap. e N≠K

Eu adicionarei que procurar por um elemento random é O(N) e não O(Log(N)) , mas neste caso queremos extrair o valor max.

 It is a simple and elegant algorithm to get first k elements of a max heap in k log(k) time. steps:- 1.construct another max heap name it auxiliary heap 2.add root element of main heap to auxiliary heap 3.pop out the element from auxiliary heap and add it's 2 children to the heap 4.do step 2 and 3 till k elements have been popped out from auxiliary heap. Add the popped element's children to the auxiliary heap.