例で説明されたJavaの優先キュー

優先キューは、実際のアプリケーションで非常に頻繁に使用されます。この記事では、優先キューとは何か、そしてJavaでそれらをどのように使用できるかを学びます。

優先キューとは何かを説明する前に、通常のキューとは何かを見てみましょう。

通常のキューは、先入れ先出し(FIFO)構造に従います。つまり、m1、m2、m3の3つのメッセージがこの順序でキューに入ると、まったく同じ順序でキューから出てきます。

なぜキューが必要なのですか?

非常に高速なデータプロデューサー(たとえば、ユーザーがWebページをクリックしたとき)があるとしましょう。しかし、後でこのデータをより遅いペースで消費したいと思います。

この場合、プロデューサーはすべてのメッセージをキューにプッシュし、コンシューマーはこれらのメッセージを後でキューからゆっくりと消費します。

優先キューとは何ですか?

前述のように、通常のキューには先入れ先出し構造があります。ただし、一部のシナリオでは、メッセージがキューに入ったタイミングではなく、優先度に基づいてキュー内のメッセージを処理する必要があります。

優先度キューは、消費者が最初に優先度の高いメッセージを消費し、次に優先度の低いメッセージを消費するのに役立ちます。

Javaの優先キュー

次に、優先度付きキューの使用方法を示す実際のJavaコードをいくつか見てみましょう。

自然順序付けの優先キュー

文字列の単純な優先度キューを作成する方法を示すコードを次に示します。

private static void testStringsNaturalOrdering() { Queue testStringsPQ = new PriorityQueue(); testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy"); System.out.println("Strings Stored in Natural Ordering in a Priority Queue\n"); while (!testStringsPQ.isEmpty()) { System.out.println(testStringsPQ.poll()); } }

最初の行は、優先キューを作成していることを示しています。

Queue testStringsPQ = new PriorityQueue();

PriorityQueueはjava.utilパッケージで利用できます。

次に、5つの文字列をランダムな順序で優先度キューに追加します。このために、以下に示すようにadd()関数を使用します。

testStringsPQ.add("abcd"); testStringsPQ.add("1234"); testStringsPQ.add("23bc"); testStringsPQ.add("zzxx"); testStringsPQ.add("abxy");

キューから最新のアイテムを取得するには、以下に示すように、poll()関数を使用します。

testStringsPQ.poll()

poll()は最新のアイテムを提供し、キューから削除します。キュー内の最新のアイテムを削除せずに取得したい場合は、peek()関数を使用できます。

testStringsPQ.peek()

最後に、以下に示すように、poll()関数を使用して、キューからすべての要素を出力します。

while (!testStringsPQ.isEmpty()) { System.out.println(testStringsPQ.poll()); }

上記のプログラムの出力は次のとおりです。

1234 23bc abcd abxy zzxx

優先度キューにコンテンツの優先順位を指定しなかったため、デフォルトの自然な順序を使用しました。この場合、文字列の昇順でデータが返されます。これは、アイテムがキューに追加された順序と同じではありません。

カスタムオーダーはどうですか?

これも可能であり、コンパレータの助けを借りてそれを行うことができます

それでは、整数優先キューを作成しましょう。しかし、今回は値の降順で結果を取得しましょう。

これを実現するには、最初に整数コンパレータを作成する必要があります。

 static class CustomIntegerComparator implements Comparator { @Override public int compare(Integer o1, Integer o2) { return o1 < o2 ? 1 : -1; } }

コンパレータを作成するために、コンパレータインターフェイスを実装し、compareメソッドをオーバーライドします。

o1 <o2を使用して1:-1結果は降順で取得されます。o1> o2を使用した場合は1:-1の場合、結果は昇順で取得されます。

コンパレータができたので、このコンパレータを優先キューに追加する必要があります。これは次のように実行できます。

Queue testIntegersPQ = new PriorityQueue(new CustomIntegerComparator());

要素を優先キューに追加して出力する残りのコードは次のとおりです。

 testIntegersPQ.add(11); testIntegersPQ.add(5); testIntegersPQ.add(-1); testIntegersPQ.add(12); testIntegersPQ.add(6); System.out.println("Integers stored in reverse order of priority in a Priority Queue\n"); while (!testIntegersPQ.isEmpty()) { System.out.println(testIntegersPQ.poll()); }

上記のプログラムの出力を以下に示します。

12 11 6 5 -1

We can see that the comparator has done its job well. Now the priority queue is giving us the integers in descending order.

Priority queue with Java objects

Up to this point, we've seen how we can use strings and integers with priority queues.

In real life applications we would generally be using priority queues with custom Java objects.

Let's first create a class called CustomerOrder which is used to store customer order details:

public class CustomerOrder implements Comparable { private int orderId; private double orderAmount; private String customerName; public CustomerOrder(int orderId, double orderAmount, String customerName) { this.orderId = orderId; this.orderAmount = orderAmount; this.customerName = customerName; } @Override public int compareTo(CustomerOrder o) { return o.orderId > this.orderId ? 1 : -1; } @Override public String toString() { return "orderId:" + this.orderId + ", orderAmount:" + this.orderAmount + ", customerName:" + customerName; } public double getOrderAmount() { return orderAmount; } }

This is a simple Java class to store customer orders. This class implements comparable interface, so that we can decide on what basis this object needs to be ordered in the priority queue.

The ordering is decided by the compareTo function in the above code. The line o.orderId > this.orderId ? 1 : -1 instructs that the orders should be sorted based on descending order of the orderId field

Below is the code which creates a priority queue for the CustomerOrder object:

CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

In the above code three customer orders have been created and added to the priority queue.

When we run this code we get the following output:

orderId:3, orderAmount:50.0, customerName:customer3 orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1

As expected, the result comes in descending order of the orderId.

What if we want to prioritize based on orderAmount?

This is again a real life scenario. Let's say that by default the CustomerOrder object is prioritized by the orderId. But then we need a way in which we can prioritize based on orderAmount.

You may immediately think that we can modify the compareTo function in the CustomerOrder class to order based on orderAmount.

But the CustomerOrder class may be used in multiple places in the application, and it would interfere with the rest of the application if we modify the compareTo function directly.

The solution to this is pretty simple: we can create a new custom comparator for the CustomerOrder class and use that along with the priority queue

Below is the code for the custom comparator:

 static class CustomerOrderComparator implements Comparator { @Override public int compare(CustomerOrder o1, CustomerOrder o2) { return o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; } }

This is very similar to the custom integer comparator we saw earlier.

The line o1.getOrderAmount() < o2.getOrderAmount() ? 1 : -1; indicates that we need to prioritize based on descending order of orderAmount.

Below is the code which creates the priority queue:

 CustomerOrder c1 = new CustomerOrder(1, 100.0, "customer1"); CustomerOrder c2 = new CustomerOrder(3, 50.0, "customer3"); CustomerOrder c3 = new CustomerOrder(2, 300.0, "customer2"); Queue customerOrders = new PriorityQueue(new CustomerOrderComparator()); customerOrders.add(c1); customerOrders.add(c2); customerOrders.add(c3); while (!customerOrders.isEmpty()) { System.out.println(customerOrders.poll()); }

In the above code we are passing the comparator to the priority queue in the following line of code:

Queue customerOrders = new PriorityQueue(new CustomerOrderComparator());

Below is the result when we run this code:

orderId:2, orderAmount:300.0, customerName:customer2 orderId:1, orderAmount:100.0, customerName:customer1 orderId:3, orderAmount:50.0, customerName:customer3

We can see that the data comes in descending order of the orderAmount.

Code

All the code discussed in this article can be found in this GitHub repo.

Congrats ?

You now know how to use priority queues in Java.

About the author

I love technology and follow the advancements in the field. I also like helping others with my technology knowledge.

Feel free to connect with me on my LinkedIn account //www.linkedin.com/in/aditya1811/

You can also follow me on twitter //twitter.com/adityasridhar18

Feel free to read more of my articles on my blog at adityasridhar.com.