Animación mostrando el funcionamiento del heapsort.
Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él. El algoritmo, después de cada extracción, recoloca en el nodo raíz o cima, la última hoja por la derecha del último nivel. Lo cual destruye la propiedad heap del árbol. Pero, a continuación realiza un proceso de "descenso" del número insertado de forma que se elige a cada movimiento el mayor de sus dos hijos, con el que se intercambia. Este intercambio, realizado sucesivamente "hunde" el nodo en el árbol restaurando la propiedad montículo del árbol y dejando paso a la siguiente extracción del nodo raíz.
El algoritmo, en su implementación habitual, tiene dos fases. Primero una fase de construcción de un montículo a partir del conjunto de elementos de entrada, y después, una fase de extracción sucesiva de la cima del montículo. La implementación del almacén de datos en el heap, pese a ser conceptualmente un árbol, puede realizarse en un vector de forma fácil. Cada nodo tiene dos hijos y por tanto, un nodo situado en la posición i del vector, tendrá a sus hijos en las posiciones 2 x i, y 2 x i +1 suponiendo que el primer elemento del vector tiene un índice = 1. Es decir, la cima ocupa la posición inicial del vector y sus dos hijos la posición segunda y tercera, y así, sucesivamente. Por tanto, en la fase de ordenación, el intercambio ocurre entre el primer elemento del vector (la raíz o cima del árbol, que es el mayor elemento del mismo) y el último elemento del vector que es la hoja más a la derecha en el último nivel. El árbol pierde una hoja y por tanto reduce su tamaño en un elemento. El vector definitivo y ordenado, empieza a construirse por el final y termina por el principio.
Descripción
He aquí una descripción en pseudocódigo del algoritmo. Se pueden encontrar descripciones de las operaciones insertar_en_monticulo y extraer_cima_del_monticulo en el artículo sobre montículos.
function heapsort(array A[0..n]): montículo M integer i; // declaro variable i for i = 0..n: insertar_en_monticulo(M, A[i]) for i = 0..n: A[i] = extraer_cima_del_monticulo(M) return A
Enlaces externos
Distintas implementaciones del algoritmo en Wikibooks (inglés)
Distintas implementaciones del algoritmo en RosettaCode.org (inglés)
Datos:Q474095
Multimedia:Heap sort
Enero 13, 2022
heapsort, este, artículo, sección, necesita, wikificado, favor, edítalo, para, cumpla, convenciones, estilo, este, aviso, puesto, junio, 2019, ordenamiento, montículos, heapsort, inglés, algoritmo, ordenamiento, recursivo, estable, complejidad, computacional, . Este articulo o seccion necesita ser wikificado por favor editalo para que cumpla con las convenciones de estilo Este aviso fue puesto el 15 de junio de 2019 El ordenamiento por monticulos heapsort en ingles es un algoritmo de ordenamiento no recursivo no estable con complejidad computacional 8 n log n displaystyle Theta n log n Animacion mostrando el funcionamiento del heapsort Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un monticulo heap y luego extraer el nodo que queda como nodo raiz del monticulo cima en sucesivas iteraciones obteniendo el conjunto ordenado Basa su funcionamiento en una propiedad de los monticulos por la cual la cima contiene siempre el menor elemento o el mayor segun se haya definido el monticulo de todos los almacenados en el El algoritmo despues de cada extraccion recoloca en el nodo raiz o cima la ultima hoja por la derecha del ultimo nivel Lo cual destruye la propiedad heap del arbol Pero a continuacion realiza un proceso de descenso del numero insertado de forma que se elige a cada movimiento el mayor de sus dos hijos con el que se intercambia Este intercambio realizado sucesivamente hunde el nodo en el arbol restaurando la propiedad monticulo del arbol y dejando paso a la siguiente extraccion del nodo raiz El algoritmo en su implementacion habitual tiene dos fases Primero una fase de construccion de un monticulo a partir del conjunto de elementos de entrada y despues una fase de extraccion sucesiva de la cima del monticulo La implementacion del almacen de datos en el heap pese a ser conceptualmente un arbol puede realizarse en un vector de forma facil Cada nodo tiene dos hijos y por tanto un nodo situado en la posicion i del vector tendra a sus hijos en las posiciones 2 x i y 2 x i 1 suponiendo que el primer elemento del vector tiene un indice 1 Es decir la cima ocupa la posicion inicial del vector y sus dos hijos la posicion segunda y tercera y asi sucesivamente Por tanto en la fase de ordenacion el intercambio ocurre entre el primer elemento del vector la raiz o cima del arbol que es el mayor elemento del mismo y el ultimo elemento del vector que es la hoja mas a la derecha en el ultimo nivel El arbol pierde una hoja y por tanto reduce su tamano en un elemento El vector definitivo y ordenado empieza a construirse por el final y termina por el principio Descripcion EditarHe aqui una descripcion en pseudocodigo del algoritmo Se pueden encontrar descripciones de las operaciones insertar en monticulo y extraer cima del monticulo en el articulo sobre monticulos function heapsort array A 0 n monticulo M integer i declaro variable i for i 0 n insertar en monticulo M A i for i 0 n A i extraer cima del monticulo M return AEnlaces externos EditarDistintas implementaciones del algoritmo en Wikibooks ingles Distintas implementaciones del algoritmo en RosettaCode org ingles Datos Q474095 Multimedia Heap sort Obtenido de https es wikipedia org w index php title Heapsort amp oldid 133274102, wikipedia, wiki, leyendo, leer, libro, biblioteca,
