heapsort

ヒープソート – ピラミッドソート。アルゴリズムの時間計算量 – O(n log n)、速いですよね?私はこれを、落ちてくる小石の選別と呼んでいます。これを説明する最も簡単な方法は視覚的に説明することだと思います。

入力は、次のような数値のリストです。
5、0、7、2、3、9、4

左から右に、データ構造、つまりバイナリツリー、または私がそれを呼んでいる – が作成されます。ピラミッド。ピラミッド要素には最大 2 つの子要素を含めることができますが、最上位の要素は 1 つだけです。

バイナリツリーを作成しましょう:
⠀⠀5
⠀0⠀7
2 3 9 4

ピラミッドを長い間見てみると、これらは配列からの単なる数値であり、次々に来て、各フロアの要素の数が 2 倍になっていることがわかります。

次に、楽しい作業が始まります。小石を落とす方法 (heapify) を使用して、ピラミッドを下から上に並べ替えましょう。最終階（2 3 9 4）から並べ替えを開始することもできますが、意味がありません。以下に転落する可能性のある床はありません。

したがって、最後から 2 番目のフロア (0 7) から要素をドロップし始めます。
⠀⠀5
⠀0⠀7
2 3 9 4

最初に該当する要素が右から選択されます。この場合は 7 です。次に、その下にあるものを調べます。その下には 9 と 4 があり、9 は 4 より大きく、9 はより大きいです。セブン！ 7 を 9 に落とし、9 を持ち上げて 7 の位置に置きます。
⠀⠀5
⠀0⠀9
2 3 7 4

次に、7 には下に落ちるところがないことがわかり、左側の最後から 2 番目の階にある番号 0 に進みます。
⠀⠀5
⠀0⠀9
2 3 7 4

その下にあるものを見てみましょう – 2 と 3、2 は 3 より小さく、3 は 0 より大きいので、0 と 3 を交換します。
⠀⠀5
⠀3⠀9
2 0 7 4

フロアの端に到達したら、上のフロアに行き、可能であればそこにすべてを落としてください。
結果はデータ構造、つまりヒープ、つまり最大ヒープになります。一番上にあるのは最大の要素です。
⠀⠀9
⠀3⠀7
2 0 5 4

これを配列表現に戻すと、リストが得られます。
[9、3、7、2、0、5、4]

このことから、最初と最後の要素を交換することで、最終的な並べ替え位置の最初の数値が得られる、つまり 9 が並べ替えられたリストの最後にあるはずであると結論付けることができ、場所を入れ替えます。
[4、3、7、2、0、5、9]

二分木を見てみましょう:
⠀⠀4
⠀3⠀7
2 0 5 9

結果は、ツリーの下の部分がソートされた状況になります。必要なのは、4 を正しい位置にドロップし、アルゴリズムを繰り返すだけです。ただし、すでにソートされている数値、つまり 9 は考慮しません。
⠀⠀4
⠀3⠀7
2 0 5 9

⠀⠀7
⠀3⠀4
2 0 5 9

⠀⠀7
⠀3⠀5
2 0 4 9

4 を落とした後、9 – の次に大きな数字を上げたことが判明しました。 7. ソートされていない最後の数字 (4) と最大の数字 (7) を交換します
⠀⠀4
⠀3⠀5
2 0 7 9

正しい最終位置に 2 つの数値があることがわかりました。
4、3、5、2、0、7、9

次に、既に並べ替えられたアルゴリズムを無視して並べ替えアルゴリズムを繰り返します。最終的にはヒープタイプ:
⠀⠀0
⠀2⠀3
4 5 7 9

またはリストとして:
0、2、3、4、5、7、9

実装

アルゴリズムは通常、次の 3 つの機能に分割されます。

<オル>

ヒープの作成

ふるい分けアルゴリズム (heapify)

ソートされていない最後の要素と最初の要素を置き換えます

ヒープは、heapify 関数を使用してバイナリツリーの最後から 2 番目の行を右から左に配列の末尾まで走査することによって作成されます。次にサイクルでは、最初の数値の置換が行われ、その後、最初の要素が配置されるか、その位置に残ります。その結果、最大の要素が 1 位に配置され、参加者が 1 人減ってサイクルが繰り返されます。各パスの後、ソートされた数値がリストの最後に残ります。

Ruby でのヒープソートの例:






module Colors



    BLUE = "\033[94m"



    RED = "\033[31m"



    STOP = "\033[0m"



end







def heapsort(rawNumbers)



    numbers = rawNumbers.dup







    def swap(numbers, from, to)



        temp = numbers[from]



        numbers[from] = numbers[to]



        numbers[to] = temp



    end







    def heapify(numbers)



        count = numbers.length()



        lastParentNode = (count - 2) / 2







        for start in lastParentNode.downto(0)



            siftDown(numbers, start, count - 1)



            start -= 1 



        end







        if DEMO



            puts "--- heapify ends ---"



        end



    end







    def siftDown(numbers, start, rightBound)      



        cursor = start



        printBinaryHeap(numbers, cursor, rightBound)







        def calculateLhsChildIndex(cursor)



            return cursor * 2 + 1



        end







        def calculateRhsChildIndex(cursor)



            return cursor * 2 + 2



        end            







        while calculateLhsChildIndex(cursor) <= rightBound



            lhsChildIndex = calculateLhsChildIndex(cursor)



            rhsChildIndex = calculateRhsChildIndex(cursor)







            lhsNumber = numbers[lhsChildIndex]



            biggerChildIndex = lhsChildIndex







            if rhsChildIndex <= rightBound



                rhsNumber = numbers[rhsChildIndex]



                if lhsNumber < rhsNumber



                    biggerChildIndex = rhsChildIndex



                end



            end







            if numbers[cursor] < numbers[biggerChildIndex]



                swap(numbers, cursor, biggerChildIndex)



                cursor = biggerChildIndex



            else



                break



            end



            printBinaryHeap(numbers, cursor, rightBound)



        end



        printBinaryHeap(numbers, cursor, rightBound)



    end







    def printBinaryHeap(numbers, nodeIndex = -1, rightBound = -1)



        if DEMO == false



            return



        end



        perLineWidth = (numbers.length() * 4).to_i



        linesCount = Math.log2(numbers.length()).ceil()



        xPrinterCount = 1



        cursor = 0



        spacing = 3



        for y in (0..linesCount)



            line = perLineWidth.times.map { " " }



            spacing = spacing == 3 ? 4 : 3



            printIndex = (perLineWidth / 2) - (spacing * xPrinterCount) / 2



            for x in (0..xPrinterCount - 1)



                if cursor >= numbers.length



                    break



                end



                if nodeIndex != -1 && cursor == nodeIndex



                    line[printIndex] = "%s%s%s" % [Colors::RED, numbers[cursor].to_s, Colors::STOP]



                elsif rightBound != -1 && cursor > rightBound



                    line[printIndex] = "%s%s%s" % [Colors::BLUE, numbers[cursor].to_s, Colors::STOP]



                else



                    line[printIndex] = numbers[cursor].to_s



                end



                cursor += 1



                printIndex += spacing



            end



            print line.join()



            xPrinterCount *= 2           



            print "\n"            



        end



    end







    heapify(numbers)



    rightBound = numbers.length() - 1







    while rightBound > 0



        swap(numbers, 0, rightBound)   



        rightBound -= 1



        siftDown(numbers, 0, rightBound)     



    end







    return numbers



end







numbersCount = 14



maximalNumber = 10



numbers = numbersCount.times.map { Random.rand(maximalNumber) }



print numbers



print "\n---\n"







start = Time.now



sortedNumbers = heapsort(numbers)



finish = Time.now



heapSortTime = start - finish







start = Time.now



referenceSortedNumbers = numbers.sort()



finish = Time.now



referenceSortTime = start - finish







print "Reference sort: "



print referenceSortedNumbers



print "\n"



print "Reference sort time: %f\n" % referenceSortTime



print "Heap sort:      "



print sortedNumbers



print "\n"



if DEMO == false



    print "Heap sort time:      %f\n" % heapSortTime



else



    print "Disable DEMO for performance measure\n"



end







if sortedNumbers != referenceSortedNumbers



    puts "Validation failed"



    exit 1



else



    puts "Validation success"



    exit 0



end

このアルゴリズムは視覚化しないと理解しにくいため、最初にバイナリツリーの現在のビューを出力する関数を作成することをお勧めします。