MÉTODO DE ORDENACIÓN 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 iteracciones 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, re coloca 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.
Implementación
package main import "fmt" func main() { var ListaDesordenada = []int{15, 3, 8, 6, 18, 1} ListaOrdenada := heapSort(ListaDesordenada) fmt.Println(ListaOrdenada) } // METODO DE ORDENACION: HEAP SORT func heapSort(ListaDesordenada []int) []int { var ListaOrdenada = []int{} N := len(ListaDesordenada) for nodo := N / 2; nodo >= 0; nodo-- { ListaOrdenada = doHeapSort(ListaDesordenada, nodo, N-1) } for nodo := N - 1; nodo >= 0; nodo-- { tmp := ListaDesordenada[0] ListaDesordenada[0] = ListaDesordenada[nodo] ListaDesordenada[nodo] = tmp ListaOrdenada = doHeapSort(ListaDesordenada, 0, nodo-1) } return ListaOrdenada } func doHeapSort(ListaDesordenada []int, nodo int, fin int) []int { izq := 2*nodo + 1 der := izq + 1 var may int if izq > fin { return ListaDesordenada } if der > fin { may = izq } else { if ListaDesordenada[izq] > ListaDesordenada[der] { may = izq } else { may = der } } if ListaDesordenada[nodo] < ListaDesordenada[may] { tmp := ListaDesordenada[nodo] ListaDesordenada[nodo] = ListaDesordenada[may] ListaDesordenada[may] = tmp doHeapSort(ListaDesordenada, may, fin) } return ListaDesordenada }Espero les sea de utilidad y hasta la próxima.
0 comentarios: