Mediana de flujo de enteros usando Heap en Java

Programación

1. Información general

En este tutorial, aprenderemos a calcular la mediana de una secuencia de números enteros.

Continuaremos indicando el problema con ejemplos, luego analizaremos el problema y finalmente implementaremos varias soluciones en Java.

2. Declaración del problema

La mediana es el valor medio de un conjunto de datos ordenados. Para un conjunto de números enteros, hay tantos elementos menores que la mediana como mayores.

En un conjunto ordenado de:

  • número impar de enteros, el elemento del medio es la mediana; en el conjunto ordenado {5, 7, 10} , la mediana es 7
  • número par de enteros, no hay elemento intermedio; la mediana se calcula como el promedio de los dos elementos intermedios; en el conjunto ordenado {5, 7, 8, 10} , la mediana es (7 + 8) / 2 = 7.5

Ahora, supongamos que en lugar de un conjunto finito, estamos leyendo números enteros de un flujo de datos. Podemos definir la mediana de un flujo de enteros como la mediana del conjunto de enteros leídos hasta ahora .

Formalicemos el enunciado del problema. Dada una entrada de un flujo de enteros, debemos diseñar una clase que realice las siguientes dos tareas para cada entero que leemos:

  1. Suma el número entero al conjunto de números enteros
  2. Encuentra la mediana de los enteros leídos hasta ahora

Por ejemplo:

add 5 // sorted-set = { 5 }, size = 1 get median -> 5 add 7 // sorted-set = { 5, 7 }, size = 2 get median -> (5 + 7) / 2 = 6 add 10 // sorted-set = { 5, 7, 10 }, size = 3 get median -> 7 add 8 // sorted-set = { 5, 7, 8, 10 }, size = 4 get median -> (7 + 8) / 2 = 7.5 ..

Aunque la secuencia no es finita, podemos asumir que podemos mantener todos los elementos de la secuencia en la memoria a la vez.

Podemos representar nuestras tareas como las siguientes operaciones en código:

void add(int num); double getMedian();

3. Enfoque ingenuo

3.1. Lista ordenada

Comencemos con una idea simple: podemos calcular la mediana de una lista ordenada de números enteros accediendo al elemento del medio o los dos elementos del medio de la lista , por índice. La complejidad de tiempo de la operación getMedian es O (1) .

Al agregar un nuevo entero, debemos determinar su posición correcta en la lista de modo que la lista permanezca ordenada. Esta operación se puede realizar en el tiempo O (n) , donde n es el tamaño de la lista . Entonces, el costo total de agregar un nuevo elemento a la lista y calcular la nueva mediana es O (n) .

3.2. Mejorando el enfoque ingenuo

La operación de adición se ejecuta en tiempo lineal, lo que no es óptimo. Intentemos abordar eso en esta sección.

Podemos dividir la lista en dos listas ordenadas : la mitad más pequeña de los enteros ordenados en orden decreciente y la mitad más grande de los enteros en orden creciente . Podemos agregar un nuevo entero en la mitad apropiada de manera que el tamaño de las listas difiera en 1, como máximo:

if element is smaller than min. element of larger half: insert into smaller half at appropriate index if smaller half is much bigger than larger half: remove max. element of smaller half and insert at the beginning of larger half (rebalance) else insert into larger half at appropriate index: if larger half is much bigger than smaller half: remove min. element of larger half and insert at the beginning of smaller half (rebalance)

Ahora, podemos calcular la mediana:

if lists contain equal number of elements: median = (max. element of smaller half + min. element of larger half) / 2 else if smaller half contains more elements: median = max. element of smaller half else if larger half contains more elements: median = min. element of larger half

Aunque solo hemos mejorado la complejidad de tiempo de la operación de adición por algún factor constante, hemos avanzado.

Analicemos los elementos a los que accedemos en las dos listas ordenadas . Potencialmente accedemos a cada elemento a medida que los desplazamos durante la operación de adición (ordenada) . Más importante aún, accedemos al mínimo y máximo (extremos) de las mitades más grande y más pequeña respectivamente, durante la operación de adición para reequilibrar y durante la operación getMedian .

Podemos ver que los extremos son los primeros elementos de sus respectivas listas . Por lo tanto, debemos optimizar para acceder al elemento en el índice 0 para cada mitad para mejorar el tiempo de ejecución general de la operación de adición .

4. Montón enfoque basado

Refinemos nuestra comprensión del problema, aplicando lo que hemos aprendido de nuestro enfoque ingenuo:

  1. Debemos obtener el elemento mínimo / máximo de un conjunto de datos en O (1) tiempo
  2. Los elementos no tienen que mantenerse ordenados siempre que podamos obtener el elemento mínimo / máximo de manera eficiente
  3. Necesitamos encontrar un enfoque para agregar un elemento a nuestro conjunto de datos que cueste menos de O (n) tiempo

A continuación, veremos la estructura de datos de Heap que nos ayuda a lograr nuestros objetivos de manera eficiente.

4.1. Estructura de datos del montón

Heap es una estructura de datos que generalmente se implementa con una matriz, pero se puede considerar como un árbol binario .

Los montones están restringidos por la propiedad del montón:

4.1.1. Max - propiedad del montón

Un nodo (hijo) no puede tener un valor mayor que el de su padre. Por lo tanto, en un montón máximo , el nodo raíz siempre tiene el valor más grande.

4.1.2. Min - propiedad del montón

Un nodo (padre) no puede tener un valor mayor que el de sus hijos. Por lo tanto, en un min-heap , el nodo raíz siempre tiene el valor más pequeño.

En Java, la clase PriorityQueue representa un montón. Avancemos a nuestra primera solución usando montones.

4.2. Primera solucion

Reemplacemos las listas en nuestro enfoque ingenuo con dos montones:

  • Un montón mínimo que contiene la mitad más grande de los elementos, con el elemento mínimo en la raíz
  • Un montón máximo que contiene la mitad más pequeña de los elementos, con el elemento máximo en la raíz

Ahora, podemos agregar el entero entrante a la mitad relevante comparándolo con la raíz del min-heap. A continuación, si después de la inserción, el tamaño de un montón difiere del otro montón en más de 1, podemos reequilibrar los montones, manteniendo así una diferencia de tamaño de como máximo 1:

if size(minHeap) > size(maxHeap) + 1: remove root element of minHeap, insert into maxHeap if size(maxHeap) > size(minHeap) + 1: remove root element of maxHeap, insert into minHeap

Con este enfoque, podemos calcular la mediana como el promedio de los elementos raíz de ambos montones, si el tamaño de los dos montones es igual. De lo contrario, el elemento raíz del montón con más elementos es la mediana .

Usaremos la clase PriorityQueue para representar los montones. La propiedad de montón predeterminada de PriorityQueue es min-heap. Podemos crear un montón máximo usando un Comparator.reverserOrder que usa el orden inverso al natural:

class MedianOfIntegerStream { private Queue minHeap, maxHeap; MedianOfIntegerStream() { minHeap = new PriorityQueue(); maxHeap = new PriorityQueue(Comparator.reverseOrder()); } void add(int num) { if (!minHeap.isEmpty() && num  minHeap.size() + 1) { minHeap.offer(maxHeap.poll()); } } else { minHeap.offer(num); if (minHeap.size() > maxHeap.size() + 1) { maxHeap.offer(minHeap.poll()); } } } double getMedian() { int median; if (minHeap.size()  maxHeap.size()) { median = minHeap.peek(); } else { median = (minHeap.peek() + maxHeap.peek()) / 2; } return median; } }

Antes de analizar el tiempo de ejecución de nuestro código, veamos la complejidad temporal de las operaciones de montón que hemos utilizado:

find-min/find-max O(1) delete-min/delete-max O(log n) insert O(log n)

Por lo tanto, la operación getMedian se puede realizar en tiempo O (1) ya que solo requiere las funciones find-min y find-max . La complejidad de tiempo de la operación de adición es O (log n) : tres llamadas de inserción / eliminación , cada una de las cuales requiere un tiempo O (log n) .

4.3. Solución invariable de tamaño de pila

En nuestro enfoque anterior, comparamos cada elemento nuevo con los elementos raíz de los montones. Exploremos otro enfoque usando heap en el que podemos aprovechar la propiedad heap para agregar un nuevo elemento en la mitad apropiada.

As we have done for our previous solution, we begin with two heaps – a min-heap and a max-heap. Next, let's introduce a condition: the size of the max-heap must be (n / 2) at all times, while the size of the min-heap can be either (n / 2) or (n / 2) + 1, depending on the total number of elements in the two heaps. In other words, we can allow only the min-heap to have an extra element, when the total number of elements is odd.

With our heap size invariant, we can compute the median as the average of the root elements of both heaps, if the sizes of both heaps are (n / 2). Otherwise, the root element of the min-heap is the median.

When we add a new integer, we have two scenarios:

1. Total no. of existing elements is even size(min-heap) == size(max-heap) == (n / 2) 2. Total no. of existing elements is odd size(max-heap) == (n / 2) size(min-heap) == (n / 2) + 1

We can maintain the invariant by adding the new element to one of the heaps and rebalancing every time:

The rebalancing works by moving the largest element from the max-heap to the min-heap, or by moving the smallest element from the min-heap to the max-heap. This way, though we're not comparing the new integer before adding it to a heap, the subsequent rebalancing ensures that we honor the underlying invariant of smaller and larger halves.

Let's implement our solution in Java using PriorityQueues:

class MedianOfIntegerStream { private Queue minHeap, maxHeap; MedianOfIntegerStream() { minHeap = new PriorityQueue(); maxHeap = new PriorityQueue(Comparator.reverseOrder()); } void add(int num) { if (minHeap.size() == maxHeap.size()) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); } else { minHeap.offer(num); maxHeap.offer(minHeap.poll()); } } double getMedian() { int median; if (minHeap.size() > maxHeap.size()) { median = minHeap.peek(); } else { median = (minHeap.peek() + maxHeap.peek()) / 2; } return median; } }

The time complexities of our operations remain unchanged: getMedian costs O(1) time, while add runs in time O(log n) with exactly the same number of operations.

Ambas soluciones basadas en montones ofrecen complejidades de tiempo y espacio similares. Si bien la segunda solución es inteligente y tiene una implementación más limpia, el enfoque no es intuitivo. Por otro lado, la primera solución sigue nuestra intuición de forma natural, y es más fácil razonar sobre la exactitud de su operación de suma .

5. Conclusión

En este tutorial, aprendimos cómo calcular la mediana de una secuencia de números enteros. Evaluamos algunos enfoques e implementamos un par de soluciones diferentes en Java usando PriorityQueue .

Como es habitual, el código fuente de todos los ejemplos está disponible en GitHub.