Veri Yapısında Öncelik Sırası: Özellikler, Türler ve Uygulama
Yayınlanan: 2021-05-02İçindekiler
Tanıtım
Veri yapısındaki öncelik sırası , “normal” sıranın bir uzantısıdır. Bir grup öğeyi içeren soyut bir veri türüdür. Kuyruktan çıkarma öğelerinin bir öncelik sırasını takip etmesi dışında “normal” sıra gibidir. Öncelik sırası, önce en yüksek önceliğe sahip olan öğeleri kuyruktan çıkarır. Bu blog size öncelik sırası ve bunun C programlama dilindeki uygulaması hakkında daha derin bir anlayış sağlayacaktır.
Öncelik Sırası nedir?
Veri kümesini korumanın bir yolunu sağlayan soyut bir veri türüdür. "Normal" kuyruk, ilk giren ilk çıkar modelini takip eder. Elemanları, ekleme işlemi sırasında takip edilen aynı sırada sıraya koyar. Ancak, bir öncelik kuyruğundaki eleman sırası, elemanın o kuyruktaki önceliğine bağlıdır. Öncelik sırası, öncelik sırasının başındaki en yüksek öncelikli öğeleri ve öncelik sırasının arkasındaki en düşük öncelikli öğeleri taşır.
Yalnızca karşılaştırılabilir öğeleri destekler. Bu nedenle, veri yapısındaki bir öncelik sırası , öğeleri artan veya azalan sırada düzenler.
Öncelik sırasını bir hastanede sırada bekleyen birkaç hasta olarak düşünebilirsiniz. Burada hastanın durumu öncelik sırasını belirler. En ağır yaralanmaya sahip hasta, sıradaki ilk kişi olacaktır.
Öncelik Sırasının Özellikleri Nelerdir?
Bir sıra, aşağıdaki özelliklere sahipse, öncelik sırası olarak adlandırılır:
- Her öğenin kendisiyle ilişkili bir önceliği vardır.
- En yüksek önceliğe sahip bir öğe öne taşınır ve önce silinir.
- İki öğe aynı öncelik değerini paylaşıyorsa, öncelik sırası, sıra dışı işlem için ilk giren ilk çıkar ilkesini takip eder.
Öncelik Sırası Türleri Nelerdir?
Öncelik sırası iki türdendir:
- Artan Sıra Öncelik Sırası
- Azalan Sıra Öncelik Sırası
Artan Sıra Öncelik Sırası
Artan bir öncelik sırası, en yüksek önceliği, o sıradaki daha düşük numaraya verir. Örneğin, öncelik kuyruğunda 4, 8, 12, 45, 35, 20 olmak üzere altı numaranız var. Öncelikle bu sayıları artan sırada sıralayacaksınız. Yeni liste şu şekildedir: 4, 8, 12, 20. 35, 45. Bu listede 4 en küçük sayıdır. Bu nedenle, artan sıralı öncelik sırası, 4 numarayı en yüksek öncelik olarak ele alır.
| 4 | 8 | 12 | 20 | 35 | 45 |
Yukarıdaki tabloda 4 en yüksek önceliğe ve 45 en düşük önceliğe sahiptir.
Azalan Sıra Öncelik Sırası
Azalan bir öncelik sırası, en yüksek önceliği, o sıradaki en yüksek sayıya verir. Örneğin, öncelik kuyruğunda 4, 8, 12, 45, 35, 20 olmak üzere altı numaranız var. Öncelikle bu sayıları artan sırada sıralayacaksınız. Yeni liste şöyle: 45, 35, 20, 12, 8, 4. Bu listede en yüksek sayı 45'tir. Bu nedenle, azalan sıra öncelik sırası, 45 sayısını en yüksek öncelik olarak ele alır.
| 45 | 35 | 20 | 12 | 8 | 4 |
Yukarıdaki tabloda 4 en düşük önceliğe ve 45 en yüksek önceliğe sahiptir.
Veri Yapısında Öncelik Sırasının Uygulanması
Öncelik sıralarını aşağıdaki yollardan biriyle uygulayabilirsiniz:
- Bağlantılı liste
- ikili yığın
- diziler
- İkili arama ağacı
İkili yığın, veri yapısında öncelik kuyruğunu uygulamak için en verimli yöntemdir .
Aşağıdaki tablolar, bir öncelik kuyruğundaki farklı işlemlerin karmaşıklığını özetlemektedir.
| Operasyon | Sırasız Dizi | Sıralı düzen | İkili Yığın | İkili Arama Ağacı |
| Sokmak | 0(1) | 0(N) | 0(günlük(N)) | 0(günlük(N)) |
| Dikizlemek | 0(N) | 0(1) | 0(1) | 0(1) |
| Silmek | 0(N) | 0(1) | 0(günlük (N)) | 0(günlük(N)) |
İkili Yığın
İkili bir yığın ağacı, ağacın tüm üst ve alt düğümlerini belirli bir sırayla düzenler. İkili bir yığın ağacında, bir üst düğümün en fazla 2 alt düğümü olabilir. Üst düğümün değeri şunlardan biri olabilir:
- alt düğümün değerine eşit veya daha az.
- alt düğümün değerine eşit veya daha fazla.
Yukarıdaki işlem, ikili yığını iki türe ayırır: maksimum yığın ve minimum yığın.
Maksimum Yığın
Maksimum yığın, bir üst düğümün alt düğüm değerine eşit veya daha büyük bir değere sahip olduğu ikili bir yığındır. Ağacın kök düğümü en yüksek değere sahiptir.
Max Heap İkili Ağaca Bir Öğe Ekleme
Veri yapısındaki öncelik kuyruğuna bir eleman/sayı eklemek için aşağıdaki adımları uygulayabilirsiniz .
- Algoritma, boş bir yuva bulmak için ağacı yukarıdan aşağıya ve soldan sağa tarar. Ardından, öğeyi ağaçtaki son düğüme ekler.
- Öğeyi yerleştirdikten sonra ikili ağacın sırası bozulur. Maksimum yığın ikili ağacının sırasını sıralamak için verileri birbiriyle değiştirmelisiniz. Ağaç max-heap özelliğini karşılayana kadar verileri karıştırmaya devam etmelisiniz.
Max Heap İkili Ağaca Bir Öğe Ekleme Algoritması
Ağaç boşsa ve düğüm içermiyorsa,
yeni bir üst düğüm newElement oluşturun.
başka (bir üst düğüm zaten mevcut)
newElement öğesini ağacın sonuna ekleyin (yani, ağacın son düğümü soldan sağa.)
ağacı maksimum yığınla
Max Heap İkili Ağaçta Bir Öğeyi Silme
- Veri Yapısında Öncelik Kuyruğundaki bir öğeyi silmek için aşağıdaki adımları uygulayabilirsiniz .
- İkili ağaçtan silmek istediğiniz öğeyi seçin.
- Ağacın sonundaki verileri, son düğüm verileriyle değiştirerek kaydırın.
- İkili ağacın son öğesini kaldırın.
- Öğeyi sildikten sonra ikili ağacın sırası bozulur. Max-heap özelliğini karşılamak için sırayı sıralamanız gerekir. Ağaç max-heap özelliğini karşılayana kadar verileri karıştırmaya devam etmelisiniz.
Max Heap İkili Ağaçtaki Bir Öğeyi Silmek için Algoritma
elementUpForDeletion, lastNode ise,
elementUpForDeletion'ı silin
yoksa elementUpForDeletion'ı lastNode ile değiştirin
elementUpForDeletion'ı silin
ağacı maksimum yığınla
Bir Maksimum Yığın İkili Ağaçta Maksimum veya Minimum Öğeyi Bulun
Bir maksimum yığın ikili ağacında, bulma işlemi ağacın üst düğümünü (en yüksek öğe) döndürür.
Bir Max Heap İkili Ağaçta Max veya Min'i Bulma Algoritması
ParentNode'u döndür
Max Heap İkili Ağacı Kullanarak Öncelik Sırasının Program Uygulaması
| #include <stdio.h> int ikili_ağaç = 10; int max_heap = 0; const int testi = 100000;
geçersiz takas( int *x, int *y ) { int a; bir = *x; *x= *y; *y = bir; }
//Max yığın ağacında üst öğeyi bulmak için kod int findParentNode(int düğüm[], int kök) { if ((root > 1) && (root <binary_tree)) { kök/2 döndür; } dönüş -1; }
void max_heapify(int düğüm[], int kök) { int leftNodeRoot = findLeftChild(düğüm, kök); int rightNodeRoot = findRightChild(düğüm, kök);
// kök, sol çocuk ve sağ çocuk arasında en yüksek bulma int en yüksek = kök;
if ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) { if (düğüm[leftNodeRoot] > düğüm[en yüksek]) { en yüksek = leftNodeRoot; } }
if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) { if (node[rightNodeRoot] > node[en yüksek]) { en yüksek = sağNodeRoot; } }
if (en yüksek != kök) { takas(&düğüm[kök], &düğüm[en yüksek]); max_heapify(düğüm, en yüksek); } }
void create_max_heap(int düğüm[]) { int d; for(d=max_heap/2; d>=1; d–) { max_heapify(düğüm, d); } }
int maksimum(int düğüm[]) { dönüş düğümü[1]; }
int find_max(int düğüm[]) { int maxNode = düğüm[1]; düğüm[1] = düğüm[maks_yığın]; max_heap–; max_heapify(düğüm, 1); maxNode'u döndür; } geçersiz iniş_key(int düğüm[], int düğüm, int anahtar) { A[kök] = anahtar; max_heapify(düğüm, kök); } void boost_key(int düğüm[], int kök, int anahtar) { düğüm[kök] = anahtar; while((root>1) && (düğüm[findParentNode(düğüm, kök)] < düğüm[kök])) { takas(&düğüm[kök], &düğüm[findParentNode(düğüm, kök)]); kök = findParentNode(düğüm, kök); } }
void ekleme(int düğüm[], int anahtarı) { max_heap++; düğüm[max_heap] = -1*test; artırma_anahtar(düğüm, max_yığın, anahtar); }
void display_heap(int düğüm[]) { int d; for(d=1; d<=maks_yığın; d++) { printf(“%d\n”,düğüm[d]); } printf(“\n”); }
int ana() { int düğüm[ikili_ağaç]; ekle(düğüm, 10); ekle(düğüm, 4); ekle(düğüm, 20); ekle(düğüm, 50); ekle(düğüm, 1); ekle(düğüm, 15);
display_heap(düğüm);
printf(“%d\n\n”, maksimum(düğüm)); display_heap(düğüm);
printf(“%d\n”, özüt_max(düğüm)); printf(“%d\n”, özüt_max(düğüm)); 0 döndür; } |
Min Yığın
Min-yığın, bir üst düğümün alt düğüm değerine eşit veya daha küçük bir değere sahip olduğu ikili bir yığındır. Ağacın kök düğümü en düşük değere sahiptir.
Minimum yığını, sırayı tersine çevirmek dışında maksimum yığınla aynı şekilde uygulayabilirsiniz.
Çözüm
Makalede verilen örnekler sadece açıklama amaçlıdır. Yukarıda verilen ifadeleri ihtiyaçlarınıza göre değiştirebilirsiniz. Bu blogda, veri yapısındaki öncelik sırası kavramını öğrendik . Veri yapısı bilginizi güçlendirmek için örneği deneyebilirsiniz.
Veri bilimi hakkında bilgi edinmek istiyorsanız, IIIT-B & upGrad'ın çalışan profesyoneller için oluşturulmuş ve 10'dan fazla vaka çalışması ve proje, uygulamalı uygulamalı atölye çalışmaları, endüstri uzmanlarıyla mentorluk, 1 Endüstri danışmanlarıyla bire bir, en iyi firmalarla 400+ saat öğrenim ve iş yardımı.
Dünyanın en iyi Üniversitelerinden çevrimiçi veri bilimi kurslarını öğrenin . Kariyerinizi hızlandırmak için Yönetici PG Programları, Gelişmiş Sertifika Programları veya Yüksek Lisans Programları kazanın.
Öncelik sırası, öğelerin önceliklerine göre eklendiği özel bir sıradır. Bu özellik, diğer çeşitli veri yapılarının uygulanmasında faydalı olur. Öncelik sırasının en popüler uygulamalarından bazıları şunlardır: Bir dizi kullanarak öncelik kuyruğunun uygulanmasında kullanılan yaklaşım basittir. Öğenin değerlerini ve önceliğini depolamak için bir yapı oluşturulur ve ardından öğeleri depolamak için o yapının dizisi oluşturulur. Bu uygulamada aşağıdaki işlemler yer alır: Aşağıda maksimum yığın ve minimum yığın arasındaki fark gösterilmektedir.Öncelik sırasının uygulamaları nelerdir?
1. Dijkstra'nın En Kısa Yol algoritması: Öncelik sırası, grafik bitişik liste şeklinde depolandığında Dijkstra'nın En Kısa Yol algoritmasında kullanılabilir.
2. Prim Algoritması: Prim'in algoritması, düğümlerin değerlerine veya anahtarlarına öncelik kuyruğunu kullanır ve her adımda bu değerlerin minimumunu çıkarır.
Veri Sıkıştırma : Huffman kodları, verileri sıkıştırmak için öncelik kuyruğunu kullanır.
İşletim Sistemleri: Öncelik sırası, yük dengeleme ve kesinti yönetimi gibi çeşitli işlemlerde işletim sistemleri için oldukça kullanışlıdır. Dizi kullanarak öncelik kuyruğunun uygulanmasında hangi yaklaşım kullanılır?
1. enqueue()-Bu işlev, öğeleri kuyruğun sonuna ekler.
2. peek() - Bu işlev, en yüksek önceliğe sahip öğeyi döndürmek için diziyi geçecektir. Aynı önceliğe sahip iki eleman bulursa, aralarındaki en yüksek değere sahip elemanı döndürür.
3. dequeue() - Bu işlev, tüm öğeleri, peek() işlevi tarafından döndürülen öğenin 1 konumu soluna kaydırır ve boyutu azaltır. max heap ve min heap arasındaki fark nedir?
Min Yığın - Bir min-yığında, kök düğümün anahtarı, alt düğümünün anahtarlarından küçük veya ona eşit olmalıdır. Artan önceliği kullanır. En küçük anahtara sahip düğüm önceliktir. En küçük öğe, diğer öğelerden önce açılır.
Maksimum Yığın - Maksimum yığında , kök düğümün anahtarı, alt düğümlerinin anahtarından büyük veya ona eşit olmalıdır. Azalan önceliği kullanır. En büyük anahtara sahip düğüm önceliktir. En büyük öğe, diğer öğelerden önce açılır.