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