Python Heapsort
Ejemplo de Python3El ordenamiento por montículos (Heapsort) es un algoritmo de ordenamiento diseñado utilizando la estructura de datos del montículo. Un montículo es una estructura de árbol binario casi completo y, al mismo tiempo, cumple con la propiedad del montículo: es decir, el valor clave o índice de los nodos hijos siempre es menor (o mayor) que el de su nodo padre. Se puede decir que el ordenamiento por montículos es un ordenamiento por selección que utiliza el concepto de montículo para ordenar.
Ejemplo
def heapify(arr, n, i):
largest = i
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # Intercambiar
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build a maxheap.
for i in range(n, -1, -1):
heapify(arr, n, i)
# Intercambiar los elementos uno a uno
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Intercambiar
heapify(arr, i, 0)
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Después de ordenar")
for i in range(n):
print ("%d" %arr[i]),
El resultado de ejecutar el código anterior es:
排序后 5 6 7 11 12 13Otras extensiones