Javaヒープの応用シナリオと実装方法の紹介-＆＃＆チュートリアル-php.cn

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

PHPz

リリース： 2023-04-24 08:28:14

転載

1669 人が閲覧しました

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. ヒープの作成

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

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

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

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

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

2. ヒープの挿入と削除

1. ヒープの挿入

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

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

[上方調整]

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 つずつ
#ヒープの最上位要素を下方に調整

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

1. ヒープの並べ替え

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

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

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

Javaヒープの応用シナリオと実装方法の紹介 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] の使用に関する注意事項:

int newCapacity = oldCapacity ((oldCapacity < 64) ?

(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)	用一个集合来创建优先级队列