Pythonでヒープソートを実装する方法（コード例）

この記事の内容はPythonでヒープソートを実装する方法(コード例)です、ある程度参考になる内容ですので、困っている方は参考にしていただければ幸いです。

ヒープ ソート

ヒープ ソートとは、ヒープのデータ構造を使用して設計されたソート アルゴリズムを指します。スタッキングは完全なバイナリ ツリーに近似する構造であり、同時にスタッキングの特性も満たします。つまり、子ノードのキー値またはインデックスは常に親ノードより小さい (または大きい) (ただし、すべての左側のサブツリーが右側のサブツリーよりも小さいという保証はありません。また、その逆も同様です)。ヒープソートは、ヒープの概念をソートに利用した選択ソートと言えます。

ビッグトップヒープ: 各ノードの値はその子ノードの値以上であり、ヒープソートアルゴリズムで昇順で使用されます;

Smallトップ ヒープ : 各ノードの値はその子ノードの値以下であり、ヒープ ソート アルゴリズムで降順で使用されます;

ヒープ ソートの平均時間計算量は Ο(nlogn) です。

アルゴリズムの手順

1. ヒープ H[0...n-1]; を作成します (**非リーフ ノードの子ノードを調整して構築します)ヒープ **)

2. ヒープの先頭 (最大値) とヒープの末尾を交換します;

3. ヒープのサイズを 1 減らして、shift_down( 0). 目的は、配列の先頭にある新しいデータを対応する位置に変換することです;

4. ヒープ サイズが 1 になるまで手順 2 を繰り返します。

Python コードの実装

def buildMaxHeap(arr):
    import math
    for i in range(math.floor(len(arr)/2),-1,-1):#构建堆由下往上构建所以用-1
        heapify(arr,i)

def heapify(arr, i):
    left = 2*i+1
    right = 2*i+2
    largest = i
    if left  arr[largest]:
        largest = left
    if right  arr[largest]:
        largest = right

    if largest != i:
        swap(arr, i, largest)
        heapify(arr, largest)

def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def heapSort(arr):
    global arrLen
    arrLen = len(arr)
    buildMaxHeap(arr)
    for i in range(len(arr)-1,0,-1):
        swap(arr,0,i)
        arrLen -=1 #每次踢掉求出的最大值
        heapify(arr, 0)
    return arr

以上がPythonでヒープソートを実装する方法（コード例）の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。