Ordenar montón en Java

1. Introducción

En este tutorial, veremos cómo funciona Heap Sort y lo implementaremos en Java.

Heap Sort se basa en la estructura de datos de Heap. Para comprender el ordenamiento de montón correctamente, primero profundizaremos en los montones y cómo se implementan.

2. Estructura de datos del montón

Un montón es una estructura de datos especializada basada en árboles . Por lo tanto, está compuesto por nodos. Asignamos los elementos a los nodos: cada nodo contiene exactamente un elemento.

Además, los nodos pueden tener hijos. Si un nodo no tiene hijos, lo llamamos hoja.

Lo que hace especial a Heap son dos cosas:

el valor de cada nodo debe ser menor o igual a todos los valores almacenados en sus hijos
es un árbol completo , lo que significa que tiene la menor altura posible

Debido a la primera regla, el elemento mínimo siempre estará en la raíz del árbol .

Cómo hacemos cumplir estas reglas depende de la implementación.

Los montones se utilizan generalmente para implementar colas de prioridad porque Heap es una implementación muy eficiente para extraer el elemento menor (o mayor).

2.1. Variantes de montón

Heap tiene muchas variantes, todas difieren en algunos detalles de implementación.

Por ejemplo, lo que describimos anteriormente es un Min-Heap, porque un padre es siempre menor que todos sus hijos . Alternativamente, podríamos haber definido Max-Heap, en cuyo caso un padre siempre es mayor que sus hijos. Por lo tanto, el elemento más grande estará en el nodo raíz.

Podemos elegir entre muchas implementaciones de árbol. El más sencillo es un árbol binario. En un árbol binario, cada nodo puede tener como máximo dos hijos. Los llamamos hijo izquierdo y hijo derecho .

La forma más sencilla de hacer cumplir la segunda regla es utilizar un árbol binario completo. Un árbol binario completo sigue algunas reglas simples:

si un nodo tiene solo un hijo, ese debería ser su hijo izquierdo
solo el nodo más a la derecha en el nivel más profundo puede tener exactamente un hijo
las hojas solo pueden estar en el nivel más profundo

Veamos estas reglas con algunos ejemplos:

 1 2 3 4 5 6 7 8 9 10 () () () () () () () () () () / \ / \ / \ / \ / \ / / / \ () () () () () () () () () () () () () () / \ / \ / \ / / \ () () () () () () () () () / ()

Los árboles 1, 2, 4, 5 y 7 siguen las reglas.

El árbol 3 y 6 violan la primera regla, el 8 y el 9 la segunda regla y el 10 viola la tercera regla.

En este tutorial, nos centraremos en Min-Heap con una implementación de árbol binario .

2.2. Insertar elementos

Debemos implementar todas las operaciones de una manera que mantenga invariantes el montón. De esta manera, podemos construir el montón con inserciones repetidas , por lo que nos centraremos en la operación de inserción única.

Podemos insertar un elemento con los siguientes pasos:

crear una nueva hoja que sea la ranura disponible más a la derecha en el nivel más profundo y almacenar el elemento en ese nodo
si el elemento es menor que su padre, los intercambiamos
continúe con el paso 2, hasta que el elemento sea menor que su padre o se convierta en la nueva raíz

Tenga en cuenta que el paso 2 no violará la regla de Heap, porque si reemplazamos el valor de un nodo con uno menor, seguirá siendo menor que sus hijos.

¡Veamos un ejemplo! Queremos insertar 4 en este montón:

 2 / \ / \ 3 6 / \ 5 7

El primer paso es crear una nueva hoja que almacene 4:

 2 / \ / \ 3 6 / \ / 5 7 4

Como 4 es menor que su padre, 6, los intercambiamos:

 2 / \ / \ 3 4 / \ / 5 7 6

Ahora comprobamos si 4 es menor que su padre o no. Dado que su padre es 2, nos detenemos. El montón sigue siendo válido e insertamos el número 4.

Insertemos 1:

 2 / \ / \ 3 4 / \ / \ 5 7 6 1

Tenemos que intercambiar 1 y 4:

 2 / \ / \ 3 1 / \ / \ 5 7 6 4

Ahora deberíamos intercambiar 1 y 2:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

Dado que 1 es la nueva raíz, nos detenemos.

3. Implementación de montón en Java

Como usamos un árbol binario completo, podemos implementarlo con una matriz : un elemento en la matriz será un nodo en el árbol. Marcamos cada nodo con los índices de la matriz de izquierda a derecha, de arriba a abajo de la siguiente manera:

 0 / \ / \ 1 2 / \ / 3 4 5

Lo único que necesitamos es realizar un seguimiento de cuántos elementos almacenamos en el árbol. De esta forma, el índice del siguiente elemento que queremos insertar será el tamaño de la matriz.

Usando esta indexación, podemos calcular el índice de los nodos padre e hijo:

padre: (índice - 1) / 2
left child: 2 * index + 1
right child: 2 * index + 2

Since we don't want to bother with array reallocating, we'll simplify the implementation even more and use an ArrayList.

A basic Binary Tree implementation looks like this:

class BinaryTree { List elements = new ArrayList(); void add(E e) { elements.add(e); } boolean isEmpty() { return elements.isEmpty(); } E elementAt(int index) { return elements.get(index); } int parentIndex(int index) { return (index - 1) / 2; } int leftChildIndex(int index) { return 2 * index + 1; } int rightChildIndex(int index) { return 2 * index + 2; } }

The code above only adds the new element to the end of the tree. Therefore, we need to traverse the new element up if necessary. We can do it with the following code:

class Heap
    
      { // ... void add(E e) { elements.add(e); int elementIndex = elements.size() - 1; while (!isRoot(elementIndex) && !isCorrectChild(elementIndex)) { int parentIndex = parentIndex(elementIndex); swap(elementIndex, parentIndex); elementIndex = parentIndex; } } boolean isRoot(int index) { return index == 0; } boolean isCorrectChild(int index) { return isCorrect(parentIndex(index), index); } boolean isCorrect(int parentIndex, int childIndex) { if (!isValidIndex(parentIndex) || !isValidIndex(childIndex)) { return true; } return elementAt(parentIndex).compareTo(elementAt(childIndex)) < 0; } boolean isValidIndex(int index) { return index < elements.size(); } void swap(int index1, int index2) { E element1 = elementAt(index1); E element2 = elementAt(index2); elements.set(index1, element2); elements.set(index2, element1); } // ... }

Note, that since we need to compare the elements, they need to implement java.util.Comparable.

4. Heap Sort

Since the root of the Heap always contains the smallest element, the idea behind Heap Sort is pretty simple: remove the root node until the Heap becomes empty.

The only thing we need is a remove operation, which keeps the Heap in a consistent state. We must ensure that we don't violate the structure of the Binary Tree or the Heap property.

To keep the structure, we can't delete any element, except the rightmost leaf. So the idea is to remove the element from the root node and store the rightmost leaf in the root node.

But this operation will most certainly violate the Heap property. So if the new root is greater than any of its child nodes, we swap it with its least child node. Since the least child node is less than all other child nodes, it doesn't violate the Heap property.

We keep swapping until the element becomes a leaf, or it's less than all of its children.

Let's delete the root from this tree:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

First, we place the last leaf in the root:

 4 / \ / \ 3 2 / \ / 5 7 6

Then, since it's greater than both of its children, we swap it with its least child, which is 2:

 2 / \ / \ 3 4 / \ / 5 7 6

4 is less than 6, so we stop.

5. Heap Sort Implementation in Java

With all we have, removing the root (popping) looks like this:

class Heap
    
      { // ... E pop() { if (isEmpty()) { throw new IllegalStateException("You cannot pop from an empty heap"); } E result = elementAt(0); int lasElementIndex = elements.size() - 1; swap(0, lasElementIndex); elements.remove(lasElementIndex); int elementIndex = 0; while (!isLeaf(elementIndex) && !isCorrectParent(elementIndex)) { int smallerChildIndex = smallerChildIndex(elementIndex); swap(elementIndex, smallerChildIndex); elementIndex = smallerChildIndex; } return result; } boolean isLeaf(int index) { return !isValidIndex(leftChildIndex(index)); } boolean isCorrectParent(int index) { return isCorrect(index, leftChildIndex(index)) && isCorrect(index, rightChildIndex(index)); } int smallerChildIndex(int index) { int leftChildIndex = leftChildIndex(index); int rightChildIndex = rightChildIndex(index); if (!isValidIndex(rightChildIndex)) { return leftChildIndex; } if (elementAt(leftChildIndex).compareTo(elementAt(rightChildIndex)) < 0) { return leftChildIndex; } return rightChildIndex; } // ... }

Like we said before, sorting is just creating a Heap, and removing the root repeatedly:

class Heap
    
      { // ... static 
     
       List sort(Iterable elements) { Heap heap = of(elements); List result = new ArrayList(); while (!heap.isEmpty()) { result.add(heap.pop()); } return result; } static 
      
        Heap of(Iterable elements) { Heap result = new Heap(); for (E element : elements) { result.add(element); } return result; } // ... }

We can verify it's working with the following test:

@Test void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList() { // given List elements = Arrays.asList(3, 5, 1, 4, 2); // when List sortedElements = Heap.sort(elements); // then assertThat(sortedElements).isEqualTo(Arrays.asList(1, 2, 3, 4, 5)); }

Note, that we could provide an implementation, which sorts in-place, which means we provide the result in the same array we got the elements. Additionally, this way we don't need any intermediate memory allocation. However, that implementation would be a bit harder to understand.

6. Time Complexity

Heap sort consists of two key steps, inserting an element and removing the root node. Both steps have the complexity O(log n).

Since we repeat both steps n times, the overall sorting complexity is O(n log n).

Note, that we didn't mention the cost of array reallocation, but since it's O(n), it doesn't affect the overall complexity. Also, as we mentioned before, it's possible to implement an in-place sorting, which means no array reallocation is necessary.

Also worth mentioning, that 50% of the elements are leaves, and 75% of elements are at the two bottommost levels. Therefore, most insert operations won't take more, than two steps.

Tenga en cuenta que, en los datos del mundo real, Quicksort suele ser más eficaz que Heap Sort. El lado positivo es que Heap Sort siempre tiene una complejidad de tiempo O (n log n) en el peor de los casos .

7. Conclusión

En este tutorial, vimos una implementación de Binary Heap y Heap Sort.

A pesar de que la complejidad del tiempo es O (n log n) , en la mayoría de los casos, no es el mejor algoritmo para datos del mundo real.

Como de costumbre, los ejemplos están disponibles en GitHub.