Problema 1: Multiway Merge

Problema: Dadas k subsecuencias ordenadas de datos, generar una secuencia ordenada.

Ejemplo, dadas las secuencias

i)   1    5    8   12   16   20
ii)  2    8   14   15   18   21
iii) 0    5    6    7   12   15

Podemos generar la secuencia

    0    1    2    5    5    6    7    8    8    12    12    14    15    15    16    18    20    21

La solución trivial para hacer esto es pegar las tres secuencias en una, y luego ordenamos esto con algún algoritmo conocido, pero esto no aprovecha el hecho de que las subsecuencias están ordenadas.

Solución

1. Consideremos un heap de tamaño k (donde k es la cantidad de subsecuencias). Los elementos de nuestro heap contienen un valor, y un índice que dice de que subsecuencia obtuvimos este valor. Consideremos un heap ordenado por menores segun el valor del elemento (no del índice).
2. Llenamos este heap con los valores menores de cada subsecuencia. Siguiendo el ejemplo el heap contendría los siguientes valores: (0,iii), (1,i), (2,ii).
3. Obtenemos el menor del heap, y luego reemplazamos este valor con el siguiente de la subsecuencia de donde sacamos el menor. En el ejemplo esto sería sacar el (0,iii) y lo reemplazamo con el (5,iii), con lo que el heap sería (1,i), (5,iii), (2,ii).
4. Seguimos haciendo esto hasta consumir todas las subsecuencias.

class Elem {
  int numLista;
  int valor;
  Elem (int N, int V) {
    this.numLista = N;
    this.valor = V;
  }
}

MergeMultiple (int k, Lista[] subsecuencias) {
  // MergeMultiple mezca k subsecuencias para obtener una secuencia ordenada
  // Las subsecuencias vienen en el arreglo de listas "subsecuencias".

  Lista resultado;
  ElemHeap h(k); // heap de Elem, padre menor que los hijos,
                 // ordenado según Elem.valor.
                 // El heap es de tamaño k,
                 // luego el heap guarda k elementos como máximo

  // rellenamos el heap "h" con los k minimos de las subsecuencias,
  // el metodo extractMin obtiene el primer elemento de la subsecuencia
  // y lo saca de la subsecuencia. Como las subsecuencias están ordenadas
  // al extraer el primero, estamos sacando el menor de la subsecuencia.
  for (int l = 1..k)
    h.insert (new Elem(l, subsecuencias[l].extractFirst()));

  while (h.size != 0) {
    Elem min = h.extractMin(); //sacamos el mínimo del heap
    // guardamos el valor en la lista de resultados al final,
    // ojo que como el heap contiene los mínimos de cada subsecuencia
    // esta inserción la estamos haciendo en orden creciente!!
    resultado.insertLast(min.valor);

    int l = min.numLista;
    // ahora tenemos que insertar un elemento de la lista l
    // (que fue de donde sacamos el mínimo)
    if (subsecuencias[l].tamaño != 0) {
      h.insert (new Elem(l, subsecuencias[l].extractFirst()));
    }
    // noten que cada vez que una subsecuencia se consume completamente,
    // el heap se hace un elemento más pequeño, luego, una vez que el
    // heap se queda sin elementos, significa que terminamos de revisar
    // todas las listas.
  }

  // ya tenemos generada la lista resultado, que contiene la lista
  // ordenada, así que la retornamos.
  return resultado;
}

Cuanto cuesta hacer esto??. En total tenemos n elementos. Cada extracción o inserción al heap cuesta O(log k). Luego el procesamiento completo cuesta O(n log k) < O(n log n) !!
 

Problema 2: Multiway Quick Select

Problema: Dado un arreglo con valores desordenados, y dado un arreglo con posiciones (por ejemplo 10, 20, 30), encontrar los elmentos que están ubicados en dichas posiciones. Por simplicidad, consideremos que los valores son todos distintos.

Esto para que sirve, por ejemplo: tenemos un arreglo con 100 elementos, y queremos conocer los elementos que dividen el conjunto en 4 subconjuntos de igual tamaño, es decir, queremos conocer los cuartiles. Para ello, nuestro
arreglo de posiciones contiene las posiciones 25, 50 y 75.

La solución trivial para hacer esto es utilizar Quick Select para seleccionar los elmentos 25, 50 y 75. Con esto hacemos tres veces Quick Select y terminamos. Cuanto cuesta esto? 3 veces el costo de Quick Select. Que tiene de malo esto?, No estoy reutilizando los cálculos.

Solución:

Junto al arreglo de posiciones "posicion", consideremos 2 arreglos adicionales:

• inicio: Inicio del segmento del arreglo que contiene a la posición buscada, inicialmente sólo tiene unos. Para nuestro ejemplo de cuartiles, inicio = {1, 1, 1}.
• fin: Fin del segmento del arreglo que contiene a la posición buscada, inicialmente sólo tiene N. Para nuestro ejemplo de cuartiles, como el conjunto tiene N = 100, fin = {100, 100, 100}.

1. Seleccionamos una posición en orden creciente l = 1..k. Para nuestro ejemplo l primero es 25, luego 50 y por último 100.
2. Seleccionamos un pivote al azar, dentro del segmento [inicio[l], fin[l]]. Hacemos el particionamiento (menores para la izquierda, mayores para la derecha). Luego de particionar el pivote queda en la posición que le corresponde (después de todos los elementos menores que él y previo a todos los que son mayores que él) le vamos a llamar i a la posición del pivote luego de particionar.
3. Con esto ajustamos los arreglos inicio y fin para todas las posiciones.

for (j=l..k) { // Para todas las posiciones que aún no se han revisado
  if (posición[j] < i) // el elemento que está en la posición posición[j] está
                       // a la izquierda del pivote.
    if (fin[j] > i)
      // podemos acortar el segmento por el lado derecho
      fin[j] = i - 1

  else if (posición[j] > i) // el elemento que está en la posición posición[j]
                            // está a la derecha del pivote.
    if (fin[j] < i)
      // podemos acortar el segmento por el lado izquierdo
      inicio[j] = i + 1

  else if (posición[j] == i) // encontramos una al elemento que está en la
                             // posición[j], como este aún no lo estoy
                             // buscando, lo dejo listo para recuperarlo
                             // cuando toque el turno de esta posición
    inicio[j] = fin[j] = i

4. Luego del ajuste, revisamos si inicio[l] = fin[l]. De ser así pasamos a la posición siguiente, sinó volvemos a 2.

if (inicio[l] = fin[l])
  // encontramos a l, y está en la posición[l], pasamos al siguiente
  l++;
else volver al paso 2

1. Cada vez que hago un particionamiento aprovecho de hacer una búsqueda para todos los índices que pueda.
2. En particular, sólo hago una vez el particionamiento sobre el conjunto completo.
3. Eventualmente habrán trozos del arreglo en los que no voy a tener que entrar.

Veamos un ejemplo:

posición[] = {20,  40,  60,  80}
inicio[] =    {1,   1,   1,   1}
fin [] =    {100, 100, 100, 100}

Empezamos buscando el elemento de posición 20. Escogemos un pivote, hacemos el particionamiento, luego de esto, supongamos que el pivote queda en la posición 55. Con esto los arreglos inicio y fin quedan indicando los siguientes segmentos:

posición[] = {20,  40,  60,  80}
inicio[] =    {1,   1,  56,  56}
fin [] =     {54,  54, 100, 100}

Escogemos un nuevo pivote en la submitad izquierda (entre 1 y 54), luego de particionar, y supongamos que el pivote queda en la posición 18. Con esto los arreglos inicio y fin quedan indicando los siguientes segmentos:

posición[] = {20,  40,  60,  80}
inicio[] =   {19,  19,  56,  56}
fin [] =     {54,  54, 100, 100}

Noten que solo cambiaron los segmentos de las posiciones 20 y 40, esto es porque el 60 y el 80 estaba en la parte derecha. Escogemos un nuevo pivote en la submitad derecha (entre 19 y 54). Luego de la partición supongamos que el pivote queda en la posición 35. Con esto:

posición[] = {20,  40,  60,  80}
inicio[] =   {19,  36,  56,  56}
fin [] =     {34,  54, 100, 100}

Escogemos un nuevo pivote entre 19 y 34, particionamos, etc...

Noten dos cosas:

1. No vamos a refinar en el segmento 1 al 18, porque ninguna de las posiciones que nos interesan estan en esta parte del arreglo.
2. Desde este momento hasta que encontremos el elemento que está en la posición 20 no podremos reutilizar los cálculos para los otros segmentos (porque están fuera del segmento en que estamos refinando el segmenti). Pero cuando nos toque buscar al elemento de posición 40, en vez de partir buscando entre las posiciones 1 y 100, vamos a buscar entre las posiciones 36 y 54, asimismo, para las posiciones 60 y 80 vamos a revisar el arreglo desde las posiciones 56 a 100, esto nos va a ahorrar trabajo.