fork download
copy 
  1. def up( child ):
  2.  
  3.     parent = child // 2
  4.  
  5.     while parent != 0:
  6.  
  7.           if Heap[parent] >= Heap[ child ]:
  8.  
  9.               aux = Heap[parent]
  10.  
  11.               Heap[parent] = Heap[child]
  12.  
  13.               Heap[child] = aux
  14.  
  15.               child = parent
  16.  
  17.               parent = child // 2
  18.           else:
  19.               break
  20.  
  21. def down( parent ):
  22.  
  23.     while 2 * parent <= sizeH:
  24.  
  25.           child = 2 * parent
  26.  
  27.           if 2 * parent + 1 <= sizeH and Heap[ 2 * parent + 1 ] < Heap[ 2 * parent ]:
  28.  
  29.               child += 1
  30.  
  31.           if Heap[parent] <= Heap[child]:
  32.  
  33.               break
  34.  
  35.           aux = Heap[ parent ]
  36.  
  37.           Heap[ parent ] = Heap[ child ]
  38.  
  39.           Heap[ child ] = aux
  40.  
  41.           parent = child
  42.  
  43.  
  44. def insertHeap( value ):
  45.  
  46.     global sizeH, Heap
  47.  
  48.     sizeH += 1
  49.  
  50.     Heap[ sizeH ] = value
  51.  
  52.     up( sizeH )
  53.  
  54.  
  55.  
  56. def removeHeap():
  57.  
  58.     global Heap, sizeH
  59.  
  60.     ret = Heap[1]
  61.     Heap[1] = Heap[sizeH]
  62.     sizeH -= 1
  63.     down(1)
  64.     return ret
  65.  
  66. def main():
  67.  
  68.     global Heap, sizeH
  69.  
  70.     arr = [9,8,7,6,5,4,2,1,0,-1,-2,-3]
  71.  
  72.     n = len(arr)
  73.  
  74.     #f = open("algsort.in","r")
  75.  
  76.     #fout = open("algsort.out","w")
  77.  
  78.     #n = int( f.readline().strip())
  79.  
  80.     #data = f.readline().strip().split(" ")
  81.  
  82.     #arr = [int(value) for value in data]
  83.  
  84.     Heap = [ 0 ] * 500500
  85.  
  86.     sizeH = 0
  87.  
  88.     for i in range(0, n):
  89.  
  90.         insertHeap( arr[ i ] )
  91.  
  92.     for i in range(0, n):
  93.  
  94.         print(removeHeap(), end = " ")
  95.         #fout.write(str(removeHeap()) + " ")
  96. main()
Success #stdin #stdout 0.04s 12624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-3 -2 -1 0 1 2 4 5 6 7 8 9
https://ideone.com/ijwMPp
Heap Sort Algorithm
language:
Python 3 (python  3.9.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!