fork download
copy 
  1. var Heap = []
  2. var sizeH = 0
  3.  
  4. function up( child ) {
  5.  
  6.       var parent = parseInt(child / 2)
  7.  
  8.       while( parent ) {
  9.  
  10.             if(Heap[parent] > Heap[child]) {
  11.  
  12.                var aux = Heap[parent]
  13.                    Heap[parent] = Heap[child]
  14.                    Heap[child] = aux
  15.  
  16.                    child = parent
  17.                    parent = parseInt(child / 2)
  18.             } else {
  19.               break
  20.             }
  21.       }
  22. }
  23.  
  24. function down( parent ) {
  25.  
  26.          while( 2 * parent <= sizeH ) {
  27.  
  28.                 var child = 2 * parent
  29.  
  30.                 if( (2 * parent + 1) <= sizeH && Heap[ 2 * parent + 1 ] < Heap[ 2 * parent ]) {
  31.  
  32.                     child += 1
  33.                 }
  34.  
  35.                 if(Heap[parent] <= Heap[child]) {
  36.                   break
  37.                 }
  38.  
  39.                 var aux = Heap[parent]
  40.                     Heap[parent] = Heap[child]
  41.                     Heap[child] = aux
  42.  
  43.                  parent = child
  44.          }
  45. }
  46.  
  47. function insertHeap( value ) {
  48.  
  49.       Heap[ ++sizeH ] = value
  50.  
  51.       up( sizeH )
  52. }
  53.  
  54. function removeHeap( ) {
  55.  
  56.        ret = Heap[ 1 ]
  57.  
  58.        Heap[ 1 ] = Heap[ sizeH ]
  59.  
  60.        sizeH -= 1
  61.  
  62.        down( 1 )
  63.  
  64.        return ret
  65.  
  66. }
  67.  
  68. function heapify( arr ) {
  69.  
  70.         n = arr.length
  71.  
  72.         for (var i = 0; i < n; i++) {
  73.  
  74.              insertHeap( arr[i] )
  75.         }
  76. }
  77.  
  78. arr = [9, 8, 7, 6, -5, -1, -3, 5]
  79.  
  80. n = arr.length
  81.  
  82. out = []
  83.  
  84. heapify( arr )
  85.  
  86. for (var i = 0; i < n; i++) {
  87.  
  88.     out.push( removeHeap() )
  89. }
  90.  
  91. print("Input:")
  92. for(var i in arr) {
  93. 	print(arr[i])
  94. }
  95.  
  96.  
  97. print("Output:")
  98. for(var i in out) {
  99. 	print(out[i])
  100. }
  101.  
  102.  
Success #stdin #stdout 0.41s 44240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Input:
9
8
7
6
-5
-1
-3
5
Output:
-5
-3
-1
5
6
7
8
9
https://ideone.com/vqzy24
Heap Sort in JavaScript
language:
JavaScript (rhino 1.7.9)
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!