Pythonのヒープソートとは何ですか？

ヒープソートは、バイナリヒープデータ構造に基づくソート手法です。ヒープソートを続行するには、バイナリツリーとバイナリヒープに精通している必要があります。

完全な二分木とは何ですか？

完全な二分木は、最後のレベルを除くすべてのレベルが完全に満たされているツリーデータ構造です。最後のレベルは左側から入力する必要があります。

バイナリヒープとは何ですか？

バイナリヒープは、バイナリツリーの特殊なケースです。バイナリヒープには2つのタイプがあります-

• 最大ヒープ-各レベルの親ノードは、その子ノードよりも大きくなっています。

• 最小ヒープ-各レベルの親ノードは、その子ノードよりも小さいです。

完全な二分木の配列表現

スペース効率が高いため、バイナリヒープは配列として表すことができます。親ノードがインデックスIに格納されている場合、左の子は2 * i + 1で計算でき、右の子は2 * i+2で計算できます。インデックスは0から始まると仮定します。

ヒープソートアルゴリズム

• 完全なバイナリツリーから最大ヒープを構築します。

• ルートを削除してヒープ内の最後の要素に置き換え、ヒープのサイズを1つ減らして、残りのノードから最大ヒープを再度構築します。

• ノードが1つだけになるまで、手順2を繰り返します。

完全なバイナリツリーから最大ヒープを構築する

これは、2つの子ノードがルートと比較される完全なバイナリツリーから最大ヒープを構築するためのコードです。 Larger要素がルートでない場合は、大きい要素をルートと交換します。これは再帰的な手順です。子ノードよりも小さい現在のルートは、正しい位置に到達しない限り、下位のサブツリーと継続的に比較されます。

次のコードは、基本的に並べ替える配列である完全なバイナリツリーから最大ヒープを構築します。

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)

ヒープソート

現時点では、最大ヒープがあります。次に、次のことを行う必要があります。

• ルートをヒープの最後の要素と交換します。

• ヒープのサイズを1つ減らします（これは、最大の要素が最後の位置に到達したことを意味します。その要素を考慮する必要はありません）。

• 最後の要素を除いて最大ヒープを再構築します。

• 要素が1つだけ残るまで、上記の手順を繰り返します。

for i in range(n-1, 0, -1):
   # Swap
   arr[i], arr[0] = arr[0], arr[i]

   # Heapify root element
   heapify(arr, i, 0)

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(arr[i], end=' ')

時間計算量-O（n logn）