Javaヒープの応用シナリオと実装方法の紹介

1. ヒープの作成

1. 下方向に調整 (小さなヒープを例にします)

調整する必要があるノードを親にマークさせ、左側に子をマークさせます親の子 (注: 親 子が存在する場合は、最初に左側の子が存在する必要があります)

親の左側の子が存在する場合、つまり、子

• 親の右の子が存在するかどうか、左右の子の中で最も小さい子を見つけて、子にマークを付けさせます

• 親と小さい子を比較します。次の場合:

親が小さい子より小さいため、調整は完了します。それ以外の場合: 親と小さい子を交換します。交換が完了すると、親の大きい要素が下に移動し、サブツリーがヒープを満たさなくなる可能性があるため、引き続き下方向に調整する必要があります、つまり、親 = 子; 子 = 親*2 1 ; そして 2 に進みます。

public void shiftDown(int[] elem,int parent,int len){
        int cur=parent*2+1;
        while(cur<len){
           if(cur+1<len){
               if(elem[cur+1]<elem[cur]){
                   cur++;
               }
           }
            if(this.elem[cur]<this.elem[parent]) {
                swap(cur, parent);
            }
            parent=cur;
            cur=parent*2+1;
        }
    }

2. ヒープの作成

通常のシーケンスの場合、ツリー全体がヒープのプロパティを満たすまで、最初の親ノードから左のノードで調整を開始する必要があります。

3. ヒープ作成の時間の複雑さ

ヒープは完全なバイナリ ツリーである必要があり、完全なバイナリ ツリーも完全なバイナリ ツリーです。次の計算から、ヒープ作成の時間計算量は O(n) です。

2. ヒープの挿入と削除

1. ヒープの挿入

• 挿入する要素をヒープの最後に配置します。配置できない場合は容量を拡張します。

• 新規挿入要素を調整します。ヒープの性質

[上方調整]

public void shiftUp(int elem[],int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[child]>elem[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

2. ヒープの削除

ヒープの性質に従って、削除された要素はヒープの最上位の要素である必要があります。手順は次のとおりです。

• ヒープの先頭要素を最後の要素と交換します。

• ヒープ内の要素の数が減ります。 1 つずつ

• #ヒープの最上位要素を下方に調整

## 3. ヒープの適用

1. ヒープの並べ替え

昇順: 大きなルート ヒープを作成します

降順: 小さなルート ヒープを作成します

ヒープの最上位要素とヒープの最後の要素を調整し、ヒープが適切になるまで下方に調整します。

2. Top-k 問題 [最小の K 数値を見つける]

top-k 問題: データ内の大きいまたは小さい上位 k 個の数値を見つけますset 要素には通常、比較的大量のデータが含まれます。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] array=new int[k];
        if(arr==null||arr.length<=k||k==0){
            return array;
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->b-a);
        int i=0;
        for(;i<k;++i){
            queue.offer(arr[i]);
        }
        while(i<arr.length){
            if(arr[i]<queue.peek()){
                queue.poll();
                queue.offer(arr[i]);
            }
            i++;
        }
        int size=queue.size();
        for(int j=0;j<size;++j){
            array[j]=queue.poll();
        }
        return array;
    }
}

IV. 共通インターフェイスの概要

1. PriorityQueue の特性

Java コレクション フレームワークには、PriorityQueue と PriorityBlockingQueue の 2 つのタイプが用意されています。 . 優先キューのタイプ。 PriorityQueue はスレッドアンセーフ、PriorityBlockingQueue はスレッドセーフですが、この記事では主に PriorityQueue について紹介します。

[PriorityQueue] の使用に関する注意事項:

PeioriryQueue のパッケージをインポートする必要があります;
配置された要素は次の機能を備えている必要がありますサイズを比較します。そうでない場合は、ClassCastException がスローされます。
null 要素を配置できません。そうでない場合は、NullPointerException がスローされます。
いくつでも挿入できます。要素は内部で自動的に展開されます;
最下層はヒープ データ構造を使用し、デフォルトは小さなヒープです。大きなヒープを構築したい場合は、コンパレータを提供する必要があります。
PriorityQueue の拡張方法:

容量が 64 未満の場合は、oldCapacity の 2 倍に拡張されます
容量が 64 以上の場合、oldCapacity の 1.5 倍に従って拡張されます。
容量が MAX_ARRAY_SIZE を超える場合、次のように拡張されます。 MAX_ARRAY_SIZE

int newCapacity = oldCapacity ((oldCapacity

(oldCapacity );

PriorityQueue は、Comparble と Comparator の 2 つのメソッドを使用します。

1. Comparble はデフォルトの内部比較メソッドです。ユーザーがカスタム タイプ オブジェクトを挿入する場合、オブジェクトは Comparble インターフェイスを実装し、compareTo メソッドをオーバーライドする必要があります。

2. ユーザーは次のこともできます。コンパレータ オブジェクトの使用を選択する場合、ユーザーがカスタム タイプ オブジェクトを挿入する場合は、Comparator インターフェイスを実装し、compare メソッドをオーバーライドするコンパレータ クラスを提供する必要があります。

// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
   @Override
   public int compare(Integer o1, Integer o2) {
      return o2-o1;
   }
}
PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());

2、优先级队列的构造

构造器	功能介绍
PriorityQueue()	创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)	创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异 常
PriorityQueue(Collection extends E> c)	用一个集合来创建优先级队列

以上がJavaヒープの応用シナリオと実装方法の紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。