問題タブ [heapsort]

Haskell の演習として、ヒープソートを実装しようとしています。ヒープは通常、命令型言語では配列として実装されますが、これは純粋な関数型言語では非常に非効率的です。そこで私はバイナリ ヒープを調べましたが、これまでに見つけたものはすべて命令的な観点からそれらを説明しており、提示されたアルゴリズムは機能的な設定に変換するのが困難です。Haskell などの純粋関数型言語でヒープを効率的に実装する方法は?

編集:効率的とは、まだ O(n*log n) である必要があることを意味しますが、C プログラムに勝る必要はありません。また、純粋に関数型プログラミングを使用したいと思います。Haskellでそれを行うことのポイントは何ですか?

ヒープソートの複雑さは最悪の場合ですがO(nlogn)、クイックソートにはありO(n^2)ます。しかし、経験的な証拠は、クイックソートが優れていることを示しています。何故ですか？

配列のすべての要素、つまり[19 18 14 15 5 7 13 3 8]が降順ではないように、配列の要素をソートするためのヒープソートのアルゴリズムが必要です。

Both quicksort and heapsort do in-place sorting. Which is better? What are the applications and cases in which either is preferred?

ヒープソートを使用してこれを降順にソートし、手順または説明を示してください。以下はツリーです

以下は配列です 79 - 33 - 57 - 8 - 25 - 48 ok 昇順は簡単です。最大の要素が一番上にあるため、最後の要素と最初の要素を交換してから、ウィキペディアのサンプル コードで説明されているように heapify を使用できます。

はっきりさせておきますが、ヒープは私が描いたツリー上に構築されています。昇順の手順はわかっていますが、配列は 8 - 25 - 33 - 48 - 57 - 79 のようになります。しかし、降順の手順は何ですか。これは非常に率直な質問です。配列を降順に並べ替えるために必要な手順を説明するだけです。

私はこれを何時間も見ていて、これを理解することはできません。heapify関数の比較がより大きい値に変更された場合、出力は本来あるべき昇順になります。リストを降順で並べ替えたいのですが、次のコードを使用しても正しい出力が得られません。

プログラム出力：

C で並べ替えプログラムを作成する必要があり、ディスク領域を節約するためにファイルを適切な場所で並べ替えることができれば便利です。データは貴重なので、プロセスが中断された場合 (ctrl-c) にファイルが破損しないようにする必要があります。マシンの電源コードが引っ張られないことを保証できます。

その他の詳細: ファイルは最大 40 GB、レコードは 128 ビット、マシンは 64 ビット、OS は POSIX

これを達成するためのヒント、または一般的なメモはありますか?

ありがとう！

明確にするために：ユーザーはプロセスをctrl-cしたいと思うでしょう。この場合、正常に終了し、データが安全であることを確認したいと考えています。したがって、この質問は、割り込みの処理と、要求された場合にすばやく終了できる並べ替えアルゴリズムの選択に関するものです。

フォローアップ（2年後）：後世のために、SIGINTハンドラーをインストールしましたが、うまく機能しました。これで電源障害を防ぐことはできませんが、対処できるリスクです。https://code.google.com/p/pawnsbfs/source/browse/trunk/hsort.cおよびhttps://code.google.com/p/pawnsbfs/source/browse/trunk/qsort.cのコード

プログラムにエラーが1つありますが、このエラーが63行に表示される理由がわかりません。

最小ヒープの配列実装で x より小さいすべてのキーを見つけるアルゴリズムを説明できる人がいますか? 実行時間を少なくとも O(k) にしたいと考えています。ここで、k は報告されたキーの数です。

私はこれでしばらく頭を悩ませてきました。

C# で HeapSort アルゴリズムの時間を確認する必要があります。私の問題は、アルゴリズムの時間を測定する方法がわからないため、 System.Timers を使用する必要があることを知っていることです。テーブルに 1000 、10 000 、100 000 、および 1000 000 の整数が含まれているアルゴリズム時間を確認する必要があります。

善良な人々を助けてください。

これはコードです：

私はあなたの助けを借りてこれを書きました, 良いですか?

{ int i; //Boulding a heap for (i = (list.Length - 1) / 2;i >=0;i--) Adjust (list, i, list.Length - 1);

}