La ordenación Heap es una técnica de ordenación por comparación basada en la estructura de datos Binary Heap. Es similar a la ordenación por selección donde primero encontramos el elemento máximo y colocamos el elemento máximo al final. Repetimos el mismo proceso para los elementos restantes.
¿Qué es el Heap Binario?
Definamos primero un Árbol Binario Completo. Un árbol binario completo es un árbol binario en el que todos los niveles, excepto posiblemente el último, están completamente llenos, y todos los nodos están tan a la izquierda como sea posible (Fuente Wikipedia)
Un montón binario es un árbol binario completo donde los elementos se almacenan en un orden especial tal que el valor en un nodo padre es mayor (o menor) que los valores en sus dos nodos hijos. El primero se denomina max heap y el segundo min-heap. El montón puede ser representado por un árbol binario o un array.
¿Por qué una representación basada en un array para un montón binario?
Dado que un montón binario es un árbol binario completo, puede ser fácilmente representado como un array y la representación basada en array es eficiente en cuanto a espacio. Si el nodo padre se almacena en el índice I, el hijo izquierdo puede ser calculado por 2 * I + 1 y el hijo derecho por 2 * I + 2 (asumiendo que la indexación comienza en 0).
Algoritmo de ordenación del montón para ordenar en orden creciente:
1. Construir un max heap a partir de los datos de entrada.
2. En este punto, el elemento más grande se almacena en la raíz del montón. Sustitúyalo por el último elemento del montón, seguido de la reducción del tamaño del montón en 1. Finalmente, heapifique la raíz del árbol.
3. Repita el paso 2 mientras el tamaño del montón sea mayor que 1.
¿Cómo construir el montón?
El procedimiento de heapificación sólo se puede aplicar a un nodo si sus nodos hijos están heapificados. Así que la heapificación debe realizarse en el orden ascendente.
Entendamos con la ayuda de un ejemplo:
Input data: 4, 10, 3, 5, 1 4(0) / \ 10(1) 3(2) / \ 5(3) 1(4)The numbers in bracket represent the indices in the array representation of data.Applying heapify procedure to index 1: 4(0) / \ 10(1) 3(2) / \5(3) 1(4)Applying heapify procedure to index 0: 10(0) / \ 5(1) 3(2) / \ 4(3) 1(4)The heapify procedure calls itself recursively to build heap in top down manner.
#include <iostream>usingnamespacestd;
voidheapify(intarr, intn, inti) {
intlargest = i;
intl = 2 * i + 1;
intr = 2 * i + 2;
if(l < n && arr > arr)
largest = l;
if(r < n && arr > arr)
largest = r;
if(largest != i) {
swap(arr, arr);
heapify(arr, n, largest);
}
}voidheapSort(intarr, intn) {
for(inti = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for(inti = n - 1; i > 0; i--) {
swap(arr, arr);
heapify(arr, i, 0);
}
}
voidprintArray(intarr, intn)
{ for(inti = 0; i < n; ++i)
cout << arr << " ";
cout << "\n";
}intmain() { intarr = { 12, 11, 13, 5, 6, 7 };
intn = sizeof(arr) / sizeof(arr); heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
}publicclassHeapSort { publicvoidsort(intarr)
{
intn = arr.length;
for(inti = n / 2- 1; i >= 0; i--)
heapify(arr, n, i);
for(inti = n - 1; i > 0; i--) {
inttemp = arr;
arr = arr;
arr = temp;
heapify(arr, i, 0);
}
}
voidheapify(intarr, intn, inti) {
intlargest = i;
intl = 2* i + 1; intr = 2* i + 2;
if(l < n && arr > arr)
largest = l;
if(r < n && arr > arr)
largest = r;
if(largest != i) {
intswap = arr;
arr = arr;
arr = swap;
heapify(arr, n, largest); }
}
staticvoidprintArray(intarr)
{
intn = arr.length;
for(inti = 0; i < n; ++i) System.out.print(arr + " ");
System.out.println();
}
publicstaticvoidmain(String args) {
intarr = { , 11, 13, 5, 6, 7};
intn = arr.length;
HeapSort ob = newHeapSort();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}defheapify(arr, n, i):
largest =i
l =2*i +1 r =2*i +2
ifl < n andarr < arr:
largest =l
ifr < n andarr < arr:
largest =r
iflargest !=i:
arr, arr =arr, arr
heapify(arr, n, largest) defheapSort(arr):
n =len(arr)
fori inrange(n//2-1, -1, -1): heapify(arr, n, i)
fori inrange(n-1, 0, -1):
arr, arr =arr, arr
heapify(arr, i, 0)
arr =heapSort(arr)n =len(arr)
print("Sorted array is")
fori inrange(n):
print("%d"%arr), usingSystem;
publicclassHeapSort {
publicvoidsort(int arr) {
intn = arr.Length;
for(inti = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for(inti = n - 1; i > 0; i--) {
inttemp = arr;
arr = arr;
arr = temp; heapify(arr, i, 0); }
}
voidheapify(int arr, intn, inti)
{
intlargest = i;
intl = 2 * i + 1;
intr = 2 * i + 2; if(l < n && arr > arr)
largest = l;
if(r < n && arr > arr)
largest = r;
if(largest != i) {
intswap = arr; arr = arr;
arr = swap;
heapify(arr, n, largest);
}
} staticvoidprintArray(int arr) {
intn = arr.Length;
for(inti = 0; i < n; ++i) Console.Write(arr + " ");
Console.Read();
}
publicstaticvoidMain()
{
int arr = { 12, 11, 13, 5, 6, 7 };
intn = arr.Length; HeapSort ob = newHeapSort(); ob.sort(arr);
Console.WriteLine("Sorted array is");
printArray(arr); } }<?phpfunctionheapify(&$arr, $n, $i) { $largest= $i;
$l= 2*$i+ 1;
$r= 2*$i+ 2;
if($l< $n&& $arr > $arr) $largest= $l;
if($r< $n&& $arr > $arr) $largest= $r;
if($largest!= $i) {
$swap= $arr;
$arr = $arr; $arr = $swap;
heapify($arr, $n, $largest);
} }
functionheapSort(&$arr, $n) {
for($i= $n/ 2 - 1; $i>= 0; $i--)
heapify($arr, $n, $i);
for($i= $n-1; $i> 0; $i--)
{
$temp= $arr;
$arr = $arr;
$arr = $temp;
heapify($arr, $i, 0);
}
}functionprintArray(&$arr, $n) { for($i= 0; $i< $n; ++$i) echo($arr." ") ; } $arr= array(12, 11, 13, 5, 6, 7); $n= sizeof($arr)/sizeof($arr); heapSort($arr, $n); echo'Sorted array is '. "\n";
printArray($arr, $n);
?>Sorted array is 5 6 7 11 12 13
Aquí está el código C anterior como referencia.
Notas:
La ordenación en pila es un algoritmo in-place.
Su implementación típica no es estable, pero puede hacerse estable (Ver esto)
Complejidad temporal: La complejidad temporal de heapify es O(Logn). La complejidad temporal de createAndBuildHeap() es O(n) y la complejidad temporal global de Heap Sort es O(nLogn).
Aplicaciones de HeapSort
1. Ordenar un array casi ordenado (o K ordenado)
2. k elementos más grandes (o más pequeños) de un array
El algoritmo Heap sort tiene usos limitados porque Quicksort y Mergesort son mejores en la práctica. Sin embargo, la propia estructura de datos Heap es enormemente utilizada. Ver Aplicaciones de la estructura de datos Heap
https://youtu.be/MtQL_ll5KhQ
Snapshots:
Cuestionario sobre la ordenación en montón
Otros algoritmos de ordenación en GeeksforGeeks/GeeksQuiz:
Ordenación rápida, Ordenación de selección, Ordenación de burbujas, Ordenación de inserción, Ordenación de fusión, Ordenación de montón, Ordenación rápida, Ordenación de radios, Ordenación de recuento, Ordenación de cubos, Ordenación de conchas, Ordenación de peines, Ordenación de casilleros
Práctica de codificación para la ordenación.