heapsort

0熱

2答えて

ヒープソートのBUILD-MAX-HEAPの実行時間がO(n)であることがわかりました。しかし、配列が降順でソートされている場合、なぜBUILD-MAX-HEAPの実行時間はO(n)になるのでしょうか？ O(1)のようなものではないですか？すでに最大値から最小値にソートされているため、MAX-HEAPIFYは必要ありません。私の理解は正しいですか？誰かがそれを私に説明してもらえますか？

1熱

1答えて

ヒープソート - 昇順と降順の並べ替えに使用するヒープ（最小/最大）

私は非常に特異なことに気付いています。この後、lectureを実行した後、C++でヒープソート用のコードを実装しました。コードは次のとおりです。 template<typename T> void min_heapify(std::vector<T> &vec, int i, int size) { int left = (2*i); //left child of a

0熱

1答えて

配列から配列unsigned intへの変更時にヒープソートCが機能しない

すべての変数と配列がintとして定義されていると、コードが正常に動作しますが、型をunsigned intに変更すると機能しません。 #include <stdio.h> #include <stdlib.h> void swap(unsigned int *a, unsigned int *b){ unsigned int temp; temp=*a ; *a=*b ; *b=t

0熱

1答えて

Heapsの最小数を出力するが、ヒープの構造を破壊しない方法は？

hackerrankerのウェブサイトでいくつかのコードを実行しているとき、heapsortを使用して、 ArrayListがコンソールから与えられますが、ツリーやヒープの構造を破壊してはいけません。私はそれは簡単だと思いますが、それを解決する方法はありませんか？だから私を助けてください。

0熱

2答えて

std :: collections :: BinaryHeapを使用したインプレース・ヒープソート

Rustでインプレース・ヒープソート関数を作成したいと考えています。標準ライブラリでは、私はstd::collections::BinaryHeapが有望であると判断しました。私は、その引数を消費する関数を作成するためにそれを使用することができる午前： use std::collections::BinaryHeap; fn heapsort<T: Ord>(list: Vec<T>) ->

1熱

1答えて

ヒープソートスレッドを使用して

私は簡単に20のサイズの配列を4つの部分に分けるためのコードを開発しています。これらの4つのスレッドはヒープソート5要素（スレッド1ソートインデックス0-4、スレッド2ソート索引5-9など）、最後にマージソート手法と一緒にマージします。マージソートは完璧に機能するので、私はそれを含めません。しかし、ヒープソート機能は正しい答えを提供することができません。スレッドは配列の14から19のインデッ

0熱

3答えて

なぜヒープソートの空間の複雑さはO（1）ですか？

ヒープソートの空間の複雑さがどのようにO（1）であるのか分かりませんか？クイックソートでは余分な配列（すなわち、インプレース）は使用されませんが、最悪の場合はO（n）、再帰呼び出しの場合はバックエンドでスタックが使用されるため、O（lg n）が最適です。私は正しい？同じことがヒープソートになります。しかし、それはインプレースですが、Build-Heap関数はMax-Heapify関数を呼び出して

1熱

1答えて

昇順および降順ヒープポート

昇順ソートと降順ソートのためにどのヒープを構築するか。ソート（昇順または降順）にヒープ（最大または最小）を使用できるかどうかを説明してください。

2熱

1答えて

CLRSの本はBUILD_MAX_HEAPがO（n log n）で漸近的にタイトではないと結論付けましたか？

CLRSブックページ157第3版。私の質問はBUILD_MAX_HEAPの複雑さがなぜO（n）であるのか、その証明ではないのかということではありません。しかし、系統的アプローチに向けて、彼らはO（n log n）で漸近的にタイトではないと結論づけた。論理的には、O（n log n）と言うのは正しいです。私が立ち往生している点は、彼らがどのようにして直感を得たかということです。もしそれがCLRSの

0熱

1答えて

TreeSortとHeapSortのアルゴリズムは何ですか？

私はwikiページと他のStackOverflow答えを読んだ。誰かがこの2つのアルゴリズムが何をするのか説明することができます。はTreesortは、二分探索木（BST）上で実行INORDERトラバーサルを使用しています