algorithm - siguiendo - Algoritmo de tiempo O(klogk) para encontrar el k-ésimo elemento más pequeño de un montón binario

nuevo algoritmo de instagram septiembre 2018

Question

Tenemos un montón binario de nodos que contiene n elementos distintos (el elemento más pequeño en la raíz). Para un k<=n , encuentre un algoritmo de tiempo O(klogk) para seleccionar el kth elemento más pequeño del montón.

O(klogn) es obvio, pero no pudo encontrar un O(klogk) . Tal vez podamos usar un segundo montón, no estoy seguro.

Answer 1

Bueno, tu intuición era correcta, necesitamos una estructura de datos adicional para lograr O (klogk) porque si simplemente realizamos operaciones en el montón original, el término logn permanecerá en la complejidad resultante.

Adivinando a partir de la complejidad objetivo O (klogk), tengo ganas de crear y mantener un montón de tamaño k para ayudarme a lograr el objetivo. Como sabrá, construir un montón de tamaño k de forma descendente toma O (klogk), lo que realmente me recuerda nuestro objetivo.

El siguiente es mi intento (no necesariamente elegante o eficiente) en un intento de alcanzar O (klogk):

1. Creamos un nuevo montón mínimo, inicializando su raíz para que sea la raíz del montón original.

2. Actualizamos el nuevo montón mínimo eliminando la raíz actual e insertando los dos elementos secundarios de la raíz actual en el montón original. Repetimos este proceso k veces.

3. El montón resultante constará de k nodos, cuya raíz es el k-ésimo elemento más pequeño en el montón original.

Notas: Los nodos en el nuevo montón deben almacenar los índices de sus nodos correspondientes en el montón original, en lugar de los valores del nodo. En cada iteración del paso 2, realmente agregamos una red de un nodo más en el nuevo montón (uno eliminado, dos insertados), k iteraciones de los cuales darán como resultado nuestro nuevo montón de tamaño k. Durante la i-ésima iteración, el nodo que se eliminará es el i-ésimo elemento más pequeño en el montón original.

Complejidad del tiempo: en cada iteración, toma O (3logk) tiempo para eliminar un elemento e insertar dos en el nuevo montón. Después de k iteraciones, es O (3klogk) = O (klogk).

Espero que esta solución te inspire un poco.

Answer 2

Suponiendo que estamos utilizando un minheap, de modo que un nodo raíz sea siempre más pequeño que sus nodos secundarios.

Create a sorted list toVisit, which contains the nodes which we will traverse next. This is initially just the root node.
Create an array smallestNodes. Initially this is empty.
While length of smallestNodes < k:
Remove the smallest Node from toVisit
add that node to smallestNodes
add that node''s children to toVisit

Cuando hayas terminado, el k-ésimo nodo más pequeño está en los Nodos más pequeños [k-1].

Dependiendo de la implementación de toVisit, puede obtener inserción en tiempo log (k) y eliminación en tiempo constante (ya que solo está eliminando el nodo superior). Eso hace que O (k * log (k)) sea total.