事前に入力のサイズを知らなくてもヒープを実装できますか？

Question

私は未知のサイズの整数の連続入力があります。任意の瞬時に、k要素を入力として受け取ったとき、私はサイズkのヒープを持っていたいと思います。あらかじめある長さの配列を初期化せずにこれをどうすれば実現できますか？

Answer 1

バイナリツリーベースのヒープの場合。サイズに関する制限を知る必要はありません。

http://interactivepython.org/runestone/static/pythonds/Trees/BinaryHeapImplementation.html

容量が不足した場合でも、アレイベースの実装では、割り当てられたサイズのトリックの倍増を使用することができます。それは同じ時間の複雑さを持つでしょう。

Use ArrayList

why use ArrayList?

Answer 2

java.util.PriorityQueueの基礎となるデータ構造はヒープです。私はあなたのデータに注文機能を持たせようとしていたヒープについて言及しています。

デフォルトのコンストラクタを使用してPriorityQueueを初期化すると、デフォルトの初期容量（11）を持つPriorityQueueが作成され、自然順序付けに従って要素が順序付けられます。カスタムComparatorを定義すると、それはあなたの制約に従って注文します。

ArrayListのような他の動的サイズのデータ​​構造では、自分自身をソートしない限りソート順の機能は提供されません。

実行ストリームのk番目に小さい/最大の要素に似た何かを解決したいと思います。はいの場合は、デフォルトコンストラクタでPriorityQueueを初期化し、現在のサイズがkであるかどうかを各要素チェックで確認できます。現在のサイズがkの場合は、制約に従って新しい要素で先頭の要素を置き換えます。

最後に、動的サイズのみが必要な場合はArrayListを使用し、ヒープのような注文は必要ありません。