ヒープソート用のPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 −配列が与えられたので、ヒープソートの概念を使用して配列を並べ替える必要があります。

ここでは、最大の要素を最後に配置します。これは、配列がソートされるまで繰り返されます。

それでは、以下の実装のソリューションを見てみましょう-

例

# heapify
def heapify(arr, n, i):
   largest = i # largest value
   l = 2 * i + 1 # left
   r = 2 * i + 2 # right
   # if left child exists
   if l < n and arr[i] < arr[l]:
      largest = l
   # if right child exits
   if r < n and arr[largest] < arr[r]:
      largest = r
   # root
   if largest != i:
      arr[i],arr[largest] = arr[largest],arr[i] # swap
      # root.
      heapify(arr, n, largest)
# sort
def heapSort(arr):
   n = len(arr)
   # maxheap
   for i in range(n, -1, -1):
      heapify(arr, n, i)
   # element extraction
   for i in range(n-1, 0, -1):
      arr[i], arr[0] = arr[0], arr[i] # swap
      heapify(arr, i, 0)
# main
arr = [2,5,3,8,6,5,4,7]
heapSort(arr)
n = len(arr)
print ("Sorted array is")
for i in range(n):
   print (arr[i],end=" ")

出力

Sorted array is
2 3 4 5 5 6 7 8

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。

結論

この記事では、ヒープソート用のPythonプログラムを作成する方法について学びました