HeapSort

# Heap Sort in python


  def heapify(arr, n, i):
      # Find largest among root and children
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
  
      if l < n and arr[i] < arr[l]:
          largest = l
  
      if r < n and arr[largest] < arr[r]:
          largest = r
  
      # If root is not largest, swap with largest and continue heapifying
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  
  
  def heapSort(arr):
      n = len(arr)
  
      # Build max heap
      for i in range(n//2, -1, -1):
          heapify(arr, n, i)
  
      for i in range(n-1, 0, -1):
          # Swap
          arr[i], arr[0] = arr[0], arr[i]
  
          # Heapify root element
          heapify(arr, i, 0)
  
  
  arr = [1, 12, 9, 5, 6, 10]
  heapSort(arr)
  n = len(arr)
  print("Sorted array is")
  for i in range(n):
      print("%d " % arr[i], end='')

Source: programiz.com

Heap sort name meaning

A sorting algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap. The heap itself has, by definition, the largest value at the top of the tree.

-1

Similar codes

5 votes142 views4 answers
Append to a tuple
Python
0 vote130 views1 answer
How to load multiple list of dictionary values which is stored in python file and load into another python file in python over loop
Python
15 votes133 views3 answers
How to import numpy in python
Python
9 votes144 views2 answers
Default flask app
Python
2 votes137 views2 answers
Module.__dict__ python
Python
1 vote125 views2 answers
How to sort nested list in python
Python
0 vote132 views1 answer
Extract only year from date python
Python
1 vote136 views1 answer
Import bokeh
Python
-3 votes148 views3 answers
Chatterbot python
Python
0 vote134 views1 answer
Conversion un type image en array python
Python