fork download 
  1. heap = [x for x in range(5)]
  2. heap = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
  3.  
  4.  
  5. def heap_sort(heap):
  6.  
  7.     heapSize = len(heap)
  8.  
  9.     def get_parent(index):
  10.         return (index-1)//2
  11.  
  12.     def get_left_child(index):
  13.         return 2*index + 1
  14.  
  15.  
  16.     def get_right_child(index):
  17.         return 2*index + 2
  18.  
  19.     def max_heapify(index):
  20.         l = get_left_child(index)
  21.         r = get_right_child(index)
  22.  
  23.         if l < heapSize and heap[l] > heap[index]:
  24.             largest = l
  25.         else:
  26.             largest = index
  27.  
  28.         if r < heapSize and heap[r] > heap[largest]:
  29.             largest = r
  30.  
  31.         if largest != index:
  32.             heap[index], heap[largest] = heap[largest], heap[index]
  33.             max_heapify(largest)
  34.  
  35.     def build_max_heap():
  36.         heapSize = len(heap)
  37.         for i in range(len(heap)//2, -1, -1):
  38.             max_heapify(i)
  39.  
  40.     build_max_heap()
  41.     j = 0
  42.     for i in range(len(heap)-1, 0, -1):
  43.         heap[0], heap[i] = heap[i], heap[0]
  44.         heapSize -= 1
  45.         j += 1
  46.         max_heapify(0)
  47.  
  48. print(heap)
  49. heap_sort(heap[:])
  50. print(heap)
Success #stdin #stdout 0.11s 10088KB
comments (?)
stdin 
Standard input is empty
stdout 
[4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
[4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
https://ideone.com/eJiSeb
language:
Python 3 (python  3.12)
created:
11 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!