fork download
copy 
  1. '''
  2. Author:
  3. Adrian Statescu <mergesortv@gmail.com>
  4.  
  5. Description:
  6. A Heap is a type of data structure. One of the interesting things about
  7. heaps is that they allow you to find the largest element in the heap
  8. in O(1) time. Recall that in certain other data structures, likes arrays,
  9. this operations takes O(n) time. Futhermore, extracting the largest element
  10. from the Heap (i.e. finding and removing it) takes O(log n) time. These properties
  11. make heaps very useful for implementing a priority queue.
  12. Intuitive view of max heap:
  13. You can view the max heap as a binary tree, where each node has two children (or fewer).
  14. and the key of each node (i.e. the number inside the node) is greater than
  15. the keys of its node. There is also min heaps, where each node is smaller than
  16. its child nodes.
  17.  
  18. The root is stored at index 1, and if a node at index i, then:
  19.  - its left child has index 2 i
  20.  - its right child has index 2 i + 1
  21.  - its parent has index [i / 2]
  22.  
  23. Time Complexity with Big O Notation:
  24.  
  25. - worst case time: O(n log n)
  26. - average case time: O(n log n)
  27. - best case time: O(n log n)
  28. '''
  29. $Heap = Array.new(500500, 0)
  30.  
  31. $sizeH = 0
  32.  
  33. def up( child )
  34.  
  35.     parent = child / 2
  36.  
  37.     while parent != 0
  38.  
  39.           if $Heap[ parent ] >= $Heap[ child ]
  40.  
  41.              aux = $Heap[ parent ]
  42.  
  43.              $Heap[ parent ] = $Heap[ child ]
  44.  
  45.              $Heap[ child ] = aux
  46.  
  47.             child = parent
  48.  
  49.             parent = child / 2
  50.           else
  51.             break
  52.           end
  53.     end
  54.  
  55. end
  56.  
  57. def down( parent )
  58.  
  59.     while 2 * parent <= $sizeH
  60.  
  61.           child = 2 * parent
  62.  
  63.           if 2 * parent + 1 <= $sizeH and $Heap[ 2 * parent + 1 ] < $Heap[ 2 * parent ]
  64.  
  65.                  child += 1
  66.           end
  67.  
  68.           if $Heap[ parent ] <= $Heap[ child ]
  69.  
  70.               break
  71.           end
  72.  
  73.           aux = $Heap[ parent ]
  74.  
  75.           $Heap[ parent ] = $Heap[ child ]
  76.  
  77.           $Heap[ child ] = aux
  78.  
  79.           parent = child
  80.  
  81.     end
  82.  
  83. end
  84.  
  85. def insertHeap( value )
  86.  
  87.     $sizeH += 1
  88.  
  89.     $Heap[ $sizeH ] = value
  90.  
  91.     up( $sizeH )
  92.  
  93. end
  94.  
  95. def removeHeap
  96.  
  97.     ret = $Heap[ 1 ]
  98.  
  99.     $Heap[ 1 ] = $Heap[ $sizeH ]
  100.  
  101.     $sizeH -= 1
  102.  
  103.     down( 1 )
  104.  
  105.     return ret
  106.  
  107. end
  108.  
  109. def main
  110.  
  111.     arr = [100,70,40,30,9,8,7,6,5,4,3,-1,-2,-3]
  112.  
  113.     p arr
  114.  
  115.     n = arr.length
  116.  
  117.     for i in 0..n-1
  118.  
  119.         insertHeap( arr[i] )
  120.     end
  121.  
  122.     for i in 0..n-1
  123.  
  124.         print removeHeap()," "
  125.     end
  126. end
  127.  
  128. main
  129.  
Success #stdin #stdout 0.01s 10444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[100, 70, 40, 30, 9, 8, 7, 6, 5, 4, 3, -1, -2, -3]
-3 -2 -1 3 4 5 6 7 8 9 30 40 70 100
https://ideone.com/DAZ7Ez
Heap Sort Algorithm
language:
Ruby (ruby 2.5.5)
created:
3 years ago
visibility:
secret

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!