問題タブ [heap]

バイナリ ヒープ構造を含む次のアルゴリズムを実行しました。

アルゴリズムが行うことは、基本的に、ルートを指定して Binary Heap をトラバースし、最小値 (つまり、ルートの値と一致する値) を保持するノードを見つけて格納することです。

現在、アルゴリズムの実行時間を Big O 表記で計算するのに問題があります。私が混乱している理由は、各ノードの左右の子をトラバースするために使用される再帰のためです。

O(1)を除くすべての操作は一定時間で実行されconcatます。しかし、このような再帰的なソリューションの実行時間を正確に計算するにはどうすればよいでしょうか?

この minheap コードについて助けが必要です:

このコードは、画面上の最後の要素をポップするときに乱数を出力することを除いて、ほとんどすべてを正しく実行します。あなたの意見は何ですか？

ありがとう！

ヒープを使用して、要素がその中にあるかどうかをO（logN）時間計算量で検索できることを思い出しました。でもいきなり詳細がわからなくなってしまいました。getmindeleteaddなどしか見つかりません。

誰かがヒントを与えることができますか？

重複の可能性：
2つの異なる概念が両方とも「ヒープ」と呼ばれるのはなぜですか？

グーグルで検索しましたが、この質問の答えが見つかりません。動的メモリ割り当てで使用されるヒープとデータ構造の間の関係は何ですか？メモリは、ヒープデータ構造と同様の方法でヒープ上に編成されていますか？もしそうなら、これは非常に奇妙に思えます。なぜなら、メモリのフェッチはランダムアクセスAFAIK（つまり、O（1））であるはずですが、ヒープからのアイテムの検索は一定時間で行われないからです。

それで、これは、いわばヒープの過負荷の意味ですか、それとも何らかの接続がありますか？

ヒープソートのこれらの機能がどのように機能しているかを誰かが明確に説明できますか？

Python には最小ヒープ用の heapq モジュールが含まれていますが、最大ヒープが必要です。Python での最大ヒープの実装には何を使用すればよいですか?

ウィキペディアは次のように述べています。

選択アルゴリズム: ヒープを使用して、最小値、最大値、最小値と最大値の両方、中央値、さらには k 番目に大きい要素を見つけることを線形時間で行うことができます。

それが言っているのは、それができるということだけであり、方法ではありません。

ヒープを使用してこれを行う方法を教えてください。

私は C++ に非常に慣れていないので、標準ライブラリから C++ で最小ヒープを作成する方法があるかどうか疑問に思っていました。

私は、Javaのオブジェクトがヒープ上にあるというJavaの本でこのステートメントを読んだばかりです。データを保存してデータを高速に取得するための最良の方法であるため、ヒープが使用されていますか？

私はデータ構造が初心者であることについてしか考えていません。スタックか何か他のものを使ってみませんか？

ヒープを使用する必要があるため、STL について検索しましたが、機能していないようです。意味を説明するコードをいくつか書きました。

そして、これは私が得るものです:

したがって、ベクトルの最大要素が正しく返されないため、ヒープとして機能しません。

それとも私は何か間違ったことをしていますか？