fork download
copy 
  1. /**
  2.  *
  3.  * Author:
  4.  * Adrian Statescu http://a...content-available-to-author-only...u.com
  5.  *
  6.  * Description:
  7.  * Heap Sort Algorithm
  8.  *
  9.  * Time Complexity with Big O Notation:
  10.  *
  11.  *              Worst-case  : O(n log n)
  12.  *              Best-case   : O(n log n)
  13.  *              Average-case: O(n log n)
  14.  *
  15.  * License:
  16.  *  MIT
  17.  *
  18.  */
  19. package main
  20.  
  21. import "fmt"
  22.  
  23. var Heap [ 500500 ]int
  24.  
  25. var sizeH int
  26.  
  27. func up(child int) {
  28.  
  29.      var parent = child / 2
  30.  
  31.      for parent != 0 {
  32.  
  33.          if Heap[ parent ] > Heap[ child ] {
  34.  
  35.             aux := Heap[ parent ]
  36.  
  37.             Heap[ parent ] = Heap[ child ]
  38.  
  39.             Heap[ child ] = aux
  40.  
  41.             child = parent
  42.  
  43.             parent = child / 2
  44.  
  45.          } else {
  46.  
  47.            break
  48.         }
  49.      }
  50.  
  51. }
  52.  
  53. func down(parent int) {
  54.  
  55.     for 2 * parent <= sizeH {
  56.  
  57.         var child = 2 * parent
  58.  
  59.         if (2 * parent + 1) <= sizeH && Heap[ 2 * parent + 1 ] < Heap[ 2 * parent ] {
  60.  
  61.                 child += 1
  62.         }
  63.  
  64.         if Heap[ parent ] <= Heap[ child ] {
  65.  
  66.            break
  67.         }
  68.  
  69.         aux := Heap[parent]
  70.  
  71.         Heap[parent] = Heap[child]
  72.  
  73.         Heap[child] = aux
  74.  
  75.         parent = child
  76.     }
  77.  
  78. }
  79.  
  80. func removeHeap() int {
  81.  
  82.      var ret = Heap[ 1 ]
  83.  
  84.          Heap[ 1 ] = Heap[ sizeH ]
  85.  
  86.          sizeH -= 1
  87.  
  88.          down( 1 )
  89.  
  90.          return ret
  91. }
  92.  
  93. func insertHeap(value int) {
  94.  
  95.     sizeH += 1
  96.  
  97.     Heap[ sizeH ] = value
  98.  
  99.     up( sizeH )
  100. }
  101.  
  102. func main() {
  103.  
  104.      arr := []int{ -15, 9, 8, 7, -50, 5, -4, -3, 2, 1, -20, 10, 20 , 30 , 40, 50}
  105.  
  106.      n := len( arr )
  107.  
  108.      for i := 0 ; i < n; i++ {
  109.  
  110.        fmt.Printf("%d ", arr[i] )
  111.  
  112.      }
  113.  
  114.      fmt.Printf("\n")
  115.  
  116.      sizeH = 0
  117.  
  118.      for _, v := range arr {
  119.  
  120.         insertHeap( v )
  121.      }
  122.  
  123.      for i := 1 ; i <= n; i++ {
  124.  
  125.          fmt.Printf("%d ", removeHeap())
  126.      }
  127. }
  128.  
Success #stdin #stdout 0s 5664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-15 9 8 7 -50 5 -4 -3 2 1 -20 10 20 30 40 50 
-50 -20 -15 -4 -3 1 2 5 7 8 9 10 20 30 40 50
https://ideone.com/Od7HQP
Heap Data Structure Heap sort Algorithm
language:
Go (go 1.12.1)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!