Implementación del método de ordenación HeapSort en Golang

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.

• Tweet
• Share
• Share
• Share
• Share