¿Cuál es la manera más rápida, al menos en teoría) para ordenar un montón?

Question

Una pila es una lista donde se aplica lo siguiente:

l[i] <= l[2*i] && l[i] <= [2*i+1]

para 0 <= i < len(list)

Estoy buscando en el lugar de la clasificación.

Answer 1

Así que usted está a mitad de camino a través de un Montón de Ordenación ya, por tener sus datos en un montón.Sólo necesita implementar la segunda parte de el montón algoritmo de ordenación.Esto debería ser más rápido que el uso de quicksort en el montón de la matriz.

Si te sientes valiente podría tener un ir en la implementación de smoothsort, que es más rápido que heapsort casi-datos ordenados.

Answer 2

Sólo utilice heap-sort.Es en el lugar.Que sería la elección más natural.

Así usted puede simplemente utilizar su montón como es y hacer algo con algún otro algoritmo.Después de volver a construir la pila de la lista ordenada.Quicksort es un buen candidato porque usted puede estar seguro de que no se ejecute en el peor caso de O(n2) de la orden, simplemente porque la pila está ya pre-ordenados.

Que puede ser más rápido si su compare-función es caro.Heap-sort tienden a evaluar el proceso de comparación de la función con bastante frecuencia.

Answer 3

La clasificación de un montón en el lugar suena como un trabajo para Montón De Ordenación.

Supongo que la memoria es limitada, integrado de la aplicación, tal vez?

Answer 4

Ya que usted ya tiene un montón, no podía usted sólo tiene que utilizar la segunda fase de la montón de ordenación?Funciona en el lugar y debe ser agradable y eficiente.

Answer 5

En lugar de la clasificación, el modo más rápido de la siguiente manera.Tenga cuidado de off-by-one errores en mi código.Tenga en cuenta que este método da una inversión de la lista ordenada que debe ser unreversed en el paso final.Si utiliza un max-heap, este problema desaparece.

La idea general es una buena:intercambiar el elemento más pequeño (en el índice 0) con el último elemento en la pila, de la burbuja de ese elemento hacia abajo hasta que el montón de la propiedad es restaurado, reduzca el tamaño de la pila por uno y repetir.

Esta no es la absoluta forma más rápida para los no-en-lugar de la clasificación como David Mackay demuestra aquí - usted puede hacer mejor por poner un elemento más probabilidades de ser el más pequeño en la parte superior de la pila en lugar de uno de la fila inferior.

El tiempo es la complejidad T(n.log n) peor de los casos - n iteraciones, posiblemente con un registro de n (la altura de la pila) pasa a través del bucle while.

for (int k=len(l)-1;k>0;k--){
swap( l, 0, k );
while (i*2 < k)
  {
int left = i*2;
int right = l*2 + 1;
int swapidx = i;
if ( l[left] < l[right] )
  {
    if (l[i] > l[left])
      {
    swapidx = left;
      }
  }
else
  {
    if (l[i] > l[right])
      {
    swapidx = right;
      }
  }

if (swapidx == i)
  {
    // Found right place in the heap, break.
    break;
  }
swap( l, i, swapidx );
i = swapidx;
  }}

// Now reverse the list in linear time:
int s = 0; 
int e = len(l)-1;
while (e > s)
  {
    swap( l, s, e );
    s++; e--:
  }

Answer 6

Leer los artículos de la parte superior de la pila, uno por uno.Básicamente lo que tienes, entonces es el montón de la especie.