Programa de heapsort en Kotlin

En este artículo, vamos a aprender cómo implementar heapsort en Kotlin ? Aquí se dará cuenta de lo que es heapsort, su algoritmo, y el programa de Kotlin .

Quicksort es un algoritmo de clasificación que utiliza binario estructura de datos montón . Un montón es una estructura de datos que podemos ver como un árbol binario casi / completa en la que cada nodo actuar como un elemento. Montones pueden montón max o montón min. En el montón max, el elemento raíz es mayor que sus niños mientras en el montón min, la raíz es más pequeño que sus niños .

Imagen de http://www.stoimen.com/

El algoritmo comienza con la construcción de un máximo de almacenamiento dinámico, a continuación, cambiar la raíz (elemento max) con el último elemento, a continuación, aplicar heapify a la pila restante, excepto el class último puesto que ya está en su posición. Esto disminuirá la longitud de la pila por una. Repita el paso hasta que todos los elementos tienen su posición.

pila de clasificación ordena los elementos dados en O (n log (n)) tiempo en todos los casos. Esto es un poco difícil de implementar que otras O (nlogn) tiempo algoritmo de ordenación es decir, tipo rápido y ordenamiento por mezcla ya que tenemos que gestionar una estructura especial de datos, es decir montón.

Algoritmos

    MAX_HEAPIFY(A.i)
1. l = left(i)
2. r = right(i);
3. if ((l <= heapSize- 1) && (A[l] > A[i]))
4. largest = l
5. else
6. largest = i
7. if ((r <= heapSize- 1) && (A[r] >A[l]))
8. largest = r
9. if (largest != i)
10. swap(A, i, largest)
11. max_heapify(A, largest)
BUILD_MAX_HEAP(A)
1. A.heapsize=A.length
2. for i =heapSize/ 2 downTo0
3. max_heapify(A, i)
HEAP_SORT(A)
1. build_Max_heap(A)
2. for i =A.size- 1 downTo1)
3. swap(A, i, 0)
4. heapSize= heapSize–1
5. max_heapify(A, 0)

fuente algoritmo de Introducción a los algoritmos por Cormen

programa para implementar heapsort en Kotlin

var heapSize = 0
fun left(i: Int): Int {
return 2 * i
}
fun right(i: Int): Int {
return 2 * i + 1
}
fun swap(A: Array<Int>, i: Int, j: Int) {
var temp = A[i]
A[i] = A[j]
A[j] = temp
}
fun max_heapify(A: Array<Int>, i: Int) {
var l = left(i);
var r = right(i);
var largest: Int;
if ((l <= heapSize - 1) && (A[l] > A[i])) {
largest = l;
} else
largest = i
if ((r <= heapSize - 1) && (A[r] > A[l])) {
largest = r
}
if (largest != i) {
swap(A, i, largest);
max_heapify(A, largest);
}
}
fun buildMaxheap(A: Array<Int>) {
heapSize = A.size
for (i in heapSize / 2 downTo 0) {
max_heapify(A, i)
}
}
fun heap_sort(A: Array<Int>) {
buildMaxheap(A)
for (i in A.size - 1 downTo 1) {
swap(A, i, 0)
heapSize = heapSize - 1
max_heapify(A, 0)
}
}
fun main(arg: Array<String>) {
print("Enter no. of elements :")
var n = readLine()!!.toInt()
println("Enter elements : ")
var A = Array(n, { 0 })
for (i in 0 until n)
A[i] = readLine()!!.toInt()
heap_sort(A)
println("Sorted array is : ")
for (i in 0 until n)
print("${A[i]} ")
}

salida

Enter no. of elements :5
Enter elements :
12
23
44
54
1
Sorted array is :
1 12 23 44 54


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *