Java Öncelik Sırası: klasik bir sıra değil

Bu makalede, Sıra arayüzünü uygulayan bir öncelik sırası olan Java sınıfını öğreniyoruz. Bir programcı normal Kuyruk Arayüzü hakkında ne bilir? Her şeyden önce, bu arayüz FIFO ilkesine veya "ilk giren ilk çıkar" ilkesine dayanmaktadır. Bu, ortak anlamıyla düzenli bir kuyruğu hatırlatır. McDrive'dan kahve almak ister misin? Arabanız pencereye ilk yaklaşansa, kahvenizi sıradaki sürücüden önce alırsınız.

Kuyruk Arayüzü bildirimi

public interface Queue<E> extends Collection<E>

Öncelik Sırası nedir?

Öncelik Sırası nedir? Her şeyden önce, arkadan bir eleman ekleme ve kafadan bir eleman çıkarma durumunda Queue arabirimini uygulayan bir sınıftır. Ancak içeride olağan bir kuyruk değil. Java öncelik kuyruğu öğelerinin sırası, öğelerin önceliğine bağlıdır. En yüksek önceliğe sahip öğe, sıranın başına taşınacaktır. En yüksek dereceli öğeyi silerseniz (sunarsanız), ikincisi kahvesini almak için başa gider. Öncelik nasıl belirlenir? Belgelere göre, öncelik sırasının öğeleri, doğal sıralamalarına göre veya hangi yapıcının kullanıldığına bağlı olarak, sıra oluşturma sırasında sağlanan bir Karşılaştırıcı tarafından sıralanır. Öncelik min yığınına dayalı bir öncelik sırası. Bunun anlamı, sıra elemanlarının sayı olması durumunda, kuyruğun ilk elemanı bu sayıların en küçüğü olacaktır. Çaylak öğrenciler bu tanımı okuduktan sonra, sıklıkla öncelik sırasının lineer anlamda sıralandığını düşünmeye başlarlar. Diğer bir deyişle, öğeleri doğal sayılar olan bir sıra kullanırsak, o zaman ilk öğe en küçük ve sonuncusu en büyük olacaktır. Bu tamamen doğru değil. Öncelik kuyruğunun gerçekte nasıl çalıştığını ve ne verdiğini anlamak için yığının nasıl çalıştığını anlamanız gerekir. Öncelik sırasının iç yapısını biraz sonra bir örnek kullanarak ele alacağız. Şimdi dış nitelikleri üzerinde duralım. o zaman ilk eleman en küçük ve sonuncusu en büyüğü olacaktır. Bu tamamen doğru değil. Öncelik kuyruğunun gerçekte nasıl çalıştığını ve ne verdiğini anlamak için yığının nasıl çalıştığını anlamanız gerekir. Öncelik sırasının iç yapısını biraz sonra bir örnek kullanarak ele alacağız. Şimdi dış nitelikleri üzerinde duralım. o zaman ilk eleman en küçük ve sonuncusu en büyüğü olacaktır. Bu tamamen doğru değil. Öncelik kuyruğunun gerçekte nasıl çalıştığını ve ne verdiğini anlamak için yığının nasıl çalıştığını anlamanız gerekir. Öncelik sırasının iç yapısını biraz sonra bir örnek kullanarak ele alacağız. Şimdi dış nitelikleri üzerinde duralım.

PriorityQueue sınıf oluşturucuları ve bildirimi

PriorityQueue sınıfı, Java'da bir öncelik sırası oluşturmak için 6 farklı yol sağlar.

• PriorityQueue() - öğelerini doğal sıralamalarına göre sıralayan varsayılan başlangıç ​​kapasitesine (11) sahip boş sıra.
• PriorityQueue(Collection c) - belirtilen koleksiyondaki öğeleri içeren boş sıra.
• PriorityQueue(int startupCapacity) - öğelerini doğal sıralamalarına göre sıralayan, belirtilen başlangıç ​​kapasitesine sahip boş sıra.
• PriorityQueue(int initialCapacity, Comparator comparator) - öğelerini belirtilen karşılaştırıcıya göre sıralayan, belirtilen başlangıç ​​kapasitesine sahip boş kuyruk.
• PriorityQueue(PriorityQueue c) - belirtilen öncelik kuyruğundaki öğeleri içeren boş sıra.
• PriorityQueue(SortedSet c) - belirtilen sıralanmış kümedeki öğeleri içeren boş sıra.

Java'daki Öncelik Kuyruğu şu şekilde bildirilir:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

PriorityQueue Oluşturma

Tamsayılardan oluşan bir öncelik kuyruğu oluşturalım. Öncelik Sırası uygulaması, Java kodu:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

Argümansız bir öncelik sırası oluşturduk. Bu durumda, öncelik sırasının başı, sıranın en küçük numarasıdır. Kafayı kaldırırsanız, bir sonraki en küçük eleman burayı alacaktır. Böylece öğeleri kuyruktan artan sırada kaldırabilirsiniz. Gerekirse Karşılaştırıcı arabirimini kullanarak sıralama ilkesini değiştirebilirsiniz.

Java PriorityQueue Yöntemleri

PriorityQueue Java sınıfı, öğeleri eklemek, kaldırmak ve kontrol etmek için önemli yöntemlere sahiptir.

Öğeleri Öncelik Sırasına Ekle

• boolean add(object), belirtilen öğeyi öncelik sırasına ekler. Başarı durumunda true döndürür. Kuyruk doluysa, yöntem bir istisna atar.
• boolean Offer(object) belirtilen öğeyi bu öncelik sırasına ekler. Kuyruk doluysa, yöntem false döndürür.

Her iki toplama işlemini de kullanabilirsiniz, çoğu durumda fark yoktur. Başlatma ve öncelik sırasına öğe ekleme ile ilgili küçük bir örnek.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

Çıktı:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

Elementlerin sıralaması biraz garip geldi, bunu daha sonra açıklayacağız.

Öncelik Kuyruğundan öğeleri alma ve kaldırma

• boolean remove(object), eğer varsa, belirtilen öğenin tek bir örneğini bu sıradan kaldırır.
• Object poll() bu kuyruğun başını alır ve kaldırır. Kuyruk boşsa null döndürür.
• void clear(), öncelik kuyruğundaki tüm öğeleri kaldırır.
• Object element(), bu kuyruğun başını kaldırmadan alır. Kuyruk boşsa NoSuchElementException atar .
• Object peek(), kuyruğun başını kaldırmadan alır. Kuyruk boşsa null döndürür.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

Çıktı:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

Gördüğünüz gibi, boş Kuyruğun başını element() yöntemini kullanarak yazdırmaya çalışmak, NoSuchElementexception hatasına yol açar .

PriorityQueue Karşılaştırıcısı

• Karşılaştırıcı karşılaştırıcı(), sıradaki öğeleri sıralamak için kullanılan karşılaştırıcıyı döndürür. Sıra, öğelerinin doğal sıralamasına göre sıralanırsa null değerini döndürür.

Java öncelik kuyruğu, karşılaştırıcılı örnek

Yukarıdaki kod örneklerinde doğal (artan) sıralama kullandık ama bazen değiştirmemiz gerekiyor. Karşılaştırıcı arayüzünü uygulayan kendi dahili karşılaştırıcı sınıfımızı oluşturduğumuz Java öncelik kuyruğu örneği. Karşılaştırıcımız öğeleri en büyükten en küçüğe sıralayacaktır.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

Çıktı:

the head of Queue = 5
5
4
3
2
1

Kuyruğun başı artık minimum değil, maksimum öğedir ve sıra tersine çevrilmiştir.

Yineleyici kullanarak PriorityQueue üzerinde yineleme

ProrityQueue, Collection çerçevesinin bir parçasıdır ve Iterable<> arabirimini uygular. Bir öncelik sırasının öğeleri üzerinde yineleme yapmak için iterator() yöntemini kullanabilirsiniz . İşte bir örnek:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

Çıktı:

1 2 4 5 3 

Daha fazla PriorityQueue yöntemi

• boolean include(Object o), sıra o öğesini içeriyorsa true değerini döndürür.
• int size(), bu kuyruktaki öğelerin sayısını döndürür.
• Object[] toArray(), bu kuyruktaki tüm öğeleri içeren bir dizi döndürür.

İşte bir örnek:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

Çıktı:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

PriorityQueue Java 8 tanımı

Priorityqueue java 8 belgelerini açarsanız, orada bir sonraki tanımı bulacaksınız: Öncelik yığınına dayalı sınırsız bir öncelik kuyruğu. Öncelik sırasının öğeleri, doğal sıralamalarına göre veya hangi yapıcının kullanıldığına bağlı olarak, sıra oluşturma sırasında sağlanan bir Karşılaştırıcı tarafından sıralanır. Bir öncelik sırası boş öğelere izin vermez. Doğal sıralamaya dayanan bir öncelik kuyruğu, karşılaştırılamaz nesnelerin eklenmesine de izin vermez (bunu yapmak ClassCastException ile sonuçlanabilir). Yığın burada çok önemli bir kelimedir. Öncelik Kuyruğu öğeleri sıralamasının özelliklerini açıklar.

PriorityQueue çalışmasının prensibi: İkili Yığın

Bir örnekle başlayalım. Sıra arabirimini uygulayan iki nesne oluşturalım. Biri LinkedList, ikincisi PriorityQueue. Her ikisinin de 5 adet Tamsayı elemanı var (1,2,3,4 ve 5) ve elemanları büyükten küçüğe doğru sıralarımıza almaya başlıyoruz. Yani ilk 5 gelir, sonra 4, 3, 2 ve sonuncusu 1 olur. Ardından sırayı kontrol etmek için her iki listeyi de yazdırın.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

Bu kodların çalışmasının sonucu şu şekildedir:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

Peki, bağlantılı liste sırası tahmin edilebilir ve anlaşılabilir. FIFO prensibine göre sıralanmıştır. 5 ile başladık, yani bu eleman sıradaki ilk eleman, sonra 4'e gidiyor ve böyle devam ediyor. Öncelik sırası hakkında ne söyleyebiliriz? Dokümanlar, öncelik sırasının öğelerinin doğal sıralarına göre veya sıra oluşturma sırasında sağlanan bir Karşılaştırıcı tarafından sıralandığını söyledi. Ancak bu sıralama doğrusal sıralama anlamında “doğal” görünmemektedir. [1, 2, 4, 5, 3] yerine [1, 2, 3, 4, 5] beklemeyi tercih ederiz. Alma sırasının neden böyle olduğunu anlamak için bir yığına dayalı öncelik kuyruğunu hatırlamalıyız. yığın nedir? İkili ağaca dayalı bir veri yapısıdır.. Yığının ana özelliği: her ebeveynin önceliği, çocuklarının önceliklerinden daha büyüktür. Her ebeveynin ikiden fazla çocuğu yoksa ve seviyelerin doldurulması yukarıdan aşağıya (aynı seviyeden - soldan sağa) gidiyorsa, bir ağacın tam bir ikili olarak adlandırıldığını hatırlatmama izin verin. İkili yığın, öğeler eklendiğinde veya çıkarıldığında kendini yeniden düzenler. Min-yığın durumunda, en küçük öğe, yerleştirme sırasına bakılmaksızın köke gider. Bu minimum yığına dayalı öncelik sırası. Bu, sayı kuyruğu öğeleri söz konusu olduğunda, kuyruğun ilk öğesinin bu sayıların en küçüğü olacağı anlamına gelir. Kökü silerseniz, bir sonraki en küçük kök olur.

Örneğimize dönelim.

Adım 1. '5'i öncelik sırasına koyuyoruz. Bir kök olur. Adım 2. '4'ü öncelik sırasına ekliyoruz. 4 <5, yani yeni eleman eskisinden daha yüksek olmalıdır. 4 bir kök olur, 5 onun sol çocuğu olur. Şimdi Java'daki veri yapısı [4, 5] Adım 3. '3' ekliyoruz. Geçici olarak bir kökün sağ çocuğu olur (4). Ancak, 3 < 4, yani yukarı kaldırmalıyız. Exchange 3 ve 4. Şimdi [3, 5, 4] gibi bir yapıya sahibiz. Adım 4. '2' ekliyoruz. 5'in sol çocuğu olur. 2<5, bu yüzden onları değiştirin. 2, 3'ün sol çocuğu olur, 2 < 3, yani bir değişim işlemi daha. Şimdi bir yapımız var [2,3,4,5] Adım 5.'1' ekliyoruz. 3'ün sağ çocuğundan 2'nin sol çocuğuna gelir ve sonra köke gider. Sonuç veri yapısı: [1,2,4,5,3] Kaldırma işlemi bir kökten başlar ve ters prosedürleri tetikler. Yani, kök olarak önce 1, sonra 2, 3, 4 ve son olarak 5'e sahibiz. Bu yüzden kaldırma işlemini poll() kullanıyoruz.

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

lineer sence çıktısında “sıraladık”:

1
2
3
4
5

Bu nedenle, öncelik sırası bazı işlemler için etkili olabilir. Her öğeyi eklemek ve silmek O(log N) zaman alır ve minimum öğeyi O(1)'de alabilirsiniz. İşte tam örnek:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

Öncelik sıralarının ikili yığınlara dayandığını, dolayısıyla öğeleri doğrusal sıralı düzende tutmadıklarını anlamak önemlidir. Kökten yaprağa kadar her yol sıralıdır ama kökten farklı yollar sıralanmamıştır. Bu, kuyruğun minimum öğesini çok hızlı bir şekilde alabileceğiniz anlamına gelir.

Öncelik sırası hakkında bilmeniz gerekenler. Kısa liste

• Öncelik Kuyruğu, NULL nesnelere izin vermez.
• PriorityQueue'ye yalnızca karşılaştırılabilir nesneler ekleyebilirsiniz.
• Öncelik kuyruğu, bir tür ikili ağaç olan min. yığın olarak oluşturulur. Minimal öğe bir köktür. Öncelik sırasının nesneleri varsayılan olarak doğal sırayla sıralanır.
• Özel siparişe ihtiyacınız varsa Karşılaştırıcıyı kullanabilirsiniz.
• PriorityQueue iş parçacığı için güvenli değildir, bu nedenle eşzamanlı bir ortamda çalışmak için PriorityBlockingQueue kullanmanız daha iyi olur.
• PriorityQueue, ekleme ve yoklama yöntemleri için O(log(n)) zamanı ve minimum öğe almak için O(1) sağlar.