Heapsort

Heapsort
Animación mostrando el funcionamiento del heapsort.

El ordenamiento por montículos (heapsort en inglés) es un algoritmo de ordenamiento no recursivo, no estable, con complejidad computacional Θ(nlog n)

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.

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 := 124578
  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


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Heapsort —   [dt. »Sortierung von Haufen«], ein 1964 von James W. J. Williams entwickelter Algorithmus, mit dem beliebige Daten in auf oder absteigender Reihenfolge sortiert werden. Er basiert auf dem 1962 von Robert W. Floyd veröffentlichten Treesort… …   Universal-Lexikon

  • Heapsort — Infobox Algorithm class=Sorting algorithm A run of the heapsort algorithm sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting… …   Wikipedia

  • Heapsort — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

  • Heapsort — …   Википедия

  • Heapsort — El ordenamiento por montículos (Heap sort en inglés) es un algoritmo de ordenación no recursivo, no estable, con complejidad computacional O(n log n). Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un …   Enciclopedia Universal

  • Heapsort — Heap|sort [ hi:psɔ:t] das; s, s <zu gleichbed. engl. heap »Haufen« u. to sort »sortieren; trennen«> schnelles internes Sortierverfahren (EDV) …   Das große Fremdwörterbuch

  • Bottom-Up-Heapsort — BottomUp Heapsort ist ein Sortieralgorithmus, der u. a. 1990 von Ingo Wegener vorgestellt wurde und im Durchschnitt besser als Quicksort arbeitet, falls man Vergleichsoperationen hinreichend stark gewichtet. Es ist eine Variante von Heapsort, die …   Deutsch Wikipedia

  • BottomUp-HeapSort — ist ein Sortieralgorithmus, der u. a. 1990 von Ingo Wegener vorgestellt wurde und im Durchschnitt besser als Quicksort arbeitet, falls man Vergleichsoperationen hinreichend stark gewichtet. Es ist eine Variante von Heapsort, die vor allem zur… …   Deutsch Wikipedia

  • BottomUp-Heapsort — ist ein Sortieralgorithmus, der u. a. 1990 von Ingo Wegener vorgestellt wurde und im Durchschnitt besser als Quicksort arbeitet, falls man Vergleichsoperationen hinreichend stark gewichtet. Es ist eine Variante von Heapsort, die vor allem zur… …   Deutsch Wikipedia

  • Haldensortierung — Der Heapsort Algorithmus beim Sortieren eines Arrays aus permutierten Werten. Der Algorithmus besteht aus zwei Schritten; im vorbereitenden Schritt wird das Array zu einem binären Heap umgeordnet, dessen Baumstruktur vor dem eigentlichen… …   Deutsch Wikipedia

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”