Coada prioritară în structura datelor: caracteristici, tipuri și implementare

Publicat: 2021-05-02

Cuprins

Introducere

Coada de prioritate din structura de date este o extensie a cozii „normale”. Este un tip de date abstracte care conține un grup de articole. Este ca coada „normală”, cu excepția faptului că elementele de scoatere din coadă urmează o ordine de prioritate. Ordinea de prioritate scoate din coada acele articole care au cea mai mare prioritate. Acest blog vă va oferi o înțelegere mai profundă a cozii de prioritate și implementarea acesteia în limbajul de programare C.

Ce este o coadă prioritară?

Este un tip de date abstract care oferă o modalitate de a menține setul de date. Coada „normală” urmează un model de primul intrat, primul ieşit. Scoate elementele din coada în aceeași ordine urmată la momentul operației de inserare. Totuși, ordinea elementelor într-o coadă de prioritate depinde de prioritatea elementului în acea coadă. Coada de prioritate mută elementele cu cea mai mare prioritate la începutul cozii de prioritate și elementele cu cea mai mică prioritate în spatele cozii de prioritate.

Acceptă doar acele elemente care sunt comparabile. Prin urmare, o coadă de prioritate în structura de date aranjează elementele în ordine crescătoare sau descrescătoare.

Vă puteți gândi la o coadă prioritară ca la câțiva pacienți care așteaptă la coadă la un spital. Aici, situația pacientului definește ordinea de prioritate. Pacientul cu cea mai gravă leziune ar fi primul la coadă.

Care sunt caracteristicile unei cozi prioritare?

O coadă este denumită coadă prioritară dacă are următoarele caracteristici:

  • Fiecare articol are o anumită prioritate asociată.
  • Un element cu cea mai mare prioritate este mutat în față și șters mai întâi.
  • Dacă două elemente împărtășesc aceeași valoare de prioritate, atunci coada de prioritate urmează principiul primul intrat, primul ieșit pentru operarea în coadă.

Care sunt tipurile de coadă prioritară?

O coadă cu prioritate este de două tipuri:

  • Coadă de prioritate pentru ordine crescătoare
  • Coadă de prioritate pentru ordinea descendentă

Coadă de prioritate pentru ordine crescătoare

O coadă de prioritate în ordine crescătoare acordă cea mai mare prioritate numărului mai mic din acea coadă. De exemplu, aveți șase numere în coada de prioritate care sunt 4, 8, 12, 45, 35, 20. În primul rând, veți aranja aceste numere în ordine crescătoare. Noua listă este următoarea: 4, 8, 12, 20. 35, 45. În această listă, 4 este cel mai mic număr. Prin urmare, coada de prioritate în ordine crescătoare tratează numărul 4 ca fiind cea mai mare prioritate.

4 8 12 20 35 45

În tabelul de mai sus, 4 are cea mai mare prioritate, iar 45 are cea mai mică prioritate.

Coadă de prioritate pentru ordinea descendentă

O coadă de prioritate în ordine descrescătoare acordă cea mai mare prioritate celui mai mare număr din acea coadă. De exemplu, aveți șase numere în coada de prioritate care sunt 4, 8, 12, 45, 35, 20. În primul rând, veți aranja aceste numere în ordine crescătoare. Noua listă este următoarea: 45, 35, 20, 12, 8, 4. În această listă, 45 este cel mai mare număr. Prin urmare, coada de prioritate în ordine descrescătoare tratează numărul 45 ca fiind cea mai mare prioritate.

45 35 20 12 8 4

În tabelul de mai sus, 4 are cea mai mică prioritate, iar 45 are cea mai mare prioritate.

Implementarea Cozii de Prioritate în Structura de Date

Puteți implementa cozile prioritare în unul dintre următoarele moduri:

  • Lista legată
  • Morman binar
  • Matrice
  • Arborele de căutare binar

Heap-ul binar este cea mai eficientă metodă de implementare a cozii de prioritate în structura de date .

Tabelele de mai jos rezumă complexitatea diferitelor operațiuni dintr-o coadă de prioritate.

Operațiune Matrice neordonată Matrice comandată Heap binar Arborele de căutare binar
Introduce 0(1) 0(N) 0(log(N)) 0(log(N))
Arunca o privire 0(N) 0(1) 0(1) 0(1)
Șterge 0(N) 0(1) 0(log (N)) 0(log(N))

Heap binar

Un arbore heap binar organizează toate nodurile părinte și secundare ale arborelui într-o anumită ordine. Într-un arbore heap binar, un nod părinte poate avea maximum 2 noduri copil. Valoarea nodului părinte poate fi fie:

  • egal sau mai mic decât valoarea unui nod copil.
  • egală sau mai mare decât valoarea unui nod copil.

Procesul de mai sus împarte heap-ul binar în două tipuri: max heap și min-heap.

Max Heap

Heap-ul maxim este un heap binar în care un nod părinte are o valoare egală sau mai mare decât valoarea nodului copil. Nodul rădăcină al arborelui are cea mai mare valoare.

Inserarea unui element într-un arbore binar Max Heap

Puteți efectua următorii pași pentru a insera un element/număr în coada de prioritate din structura de date .

  1. Algoritmul scanează arborele de sus în jos și de la stânga la dreapta pentru a găsi un slot gol. Apoi inserează elementul la ultimul nod din arbore.
  2. După introducerea elementului, ordinea arborelui binar este perturbată. Trebuie să schimbați datele între ele pentru a sorta ordinea arborelui binar al heap-ului maxim. Trebuie să continuați să amestecați datele până când arborele satisface proprietatea max-heap.

Algoritm pentru inserarea unui element într-un arbore binar Max Heap

Dacă arborele este gol și nu conține niciun nod,

creați un nou nod părinte newElement.

else (un nod părinte este deja disponibil)

introduceți elementul nou la sfârșitul arborelui (adică ultimul nod al arborelui de la stânga la dreapta).

max-heapify copacul

Ștergerea unui element dintr-un arbore binar Max Heap

  1. Puteți efectua următorii pași pentru a șterge un element din Coada de prioritate din Structura datelor .
  2. Alegeți elementul pe care doriți să-l ștergeți din arborele binar.
  3. Schimbați datele la sfârșitul arborelui schimbându-le cu ultimele date de nod.
  4. Eliminați ultimul element al arborelui binar.
  5. După ștergerea elementului, ordinea arborelui binar este perturbată. Trebuie să sortați ordinea pentru a satisface proprietatea de max-heap. Trebuie să continuați să amestecați datele până când arborele îndeplinește proprietatea max-heap.

Algoritm pentru ștergerea unui element dintr-un arbore binar Max Heap

Dacă elementulUpForDeletion este ultimul Nod,

ștergeți elementulUpForDeletion

altfel înlocuiți elementUpForDeletion cu lastNode

ștergeți elementulUpForDeletion

max-heapify copacul

Găsiți elementul maxim sau minim într-un arbore binar Max Heap

Într-un arbore binar maxim heap, operația de căutare returnează nodul părinte (cel mai înalt element) al arborelui.

Algoritm pentru a găsi valoarea maximă sau minimă într-un arbore binar din grămada maximă

returnează ParentNode

Implementarea programului a cozii de prioritate folosind arborele binar Max Heap

#include <stdio.h>

int arbore_binar = 10;

int max_heap = 0;

test const int = 100000;

void swap( int *x, int *y ) {

int a;

a = *x;

*x= *y;

*y = a;

}

//Cod pentru a găsi părintele în arborele heap maxim

int findParentNode(int node[], int root) {

dacă ((rădăcină > 1) && (rădăcină < arbore_binar)) {

returnează root/2;

}

întoarcere -1;

}

void max_heapify(int node[], int root) {

int leftNodeRoot = findLeftChild(nod, root);

int rightNodeRoot = findRightChild(nod, root);

// găsirea cea mai mare între rădăcină, copilul stâng și copilul drept

int highest = rădăcină;

if ((leftNodeRoot <= max_heap) && (leftNodeRoot >0)) {

if (nod[leftNodeRoot] > nod[highest]) {

cel mai înalt = leftNodeRoot;

}

}

if ((rightNodeRoot <= max_heap) && (rightNodeRoot >0)) {

if (nod[rightNodeRoot] > nod[highest]) {

cel mai mare = rightNodeRoot;

}

}

dacă (cel mai mare != rădăcină) {

swap(&nod[root], &node[highest]);

max_heapify(nodul, cel mai mare);

}

}

void create_max_heap(int node[]) {

int d;

for(d=max_heap/2; d>=1; d–) {

max_heapify(nodul, d);

}

}

int maxim(int nod[]) {

return nodul[1];

}

int find_max(int ​​node[]) {

int maxNode = nod[1];

nod[1] = nod[max_heap];

max_heap–;

max_heapify(nodul, 1);

return maxNode;

}

void descend_key(int node[], int node, int cheie) {

A[rădăcină] = cheie;

max_heapify(nod, rădăcină);

}

void creștere_key(int node[], int rădăcină, int cheie) {

nod[rădăcină] = cheie;

while((rădăcină>1) && (nod[findParentNode(nod, rădăcină)] <nod[rădăcină])) {

swap(&nod[rădăcină], &nod[findParentNode(nod, rădăcină)]);

root = findParentNode(nod, root);

}

}

void insert(int node[], int key) {

max_heap++;

nod[max_heap] = -1*test;

creste_cheie(nod, max_heap, cheie);

}

void display_heap(int node[]) {

int d;

for(d=1; d<=max_heap; d++) {

printf(„%d\n”,nodul[d]);

}

printf(“\n”);

}

int main() {

int nod[arbore_binar];

insert(nodul, 10);

insert(nod, 4);

insert (nodul, 20);

insert (nodul, 50);

insert(nod, 1);

insert (nodul, 15);

display_heap(nod);

printf(“%d\n\n”, maximum(nodul));

display_heap(nod);

printf(“%d\n”, extract_max(nod));

printf(“%d\n”, extract_max(nod));

returnează 0;

}

Min Heap

Heap-ul min este un heap binar în care un nod părinte are o valoare egală sau mai mică decât valoarea nodului copil. Nodul rădăcină al arborelui are cea mai mică valoare.

Puteți implementa min-heap-ul în același mod ca și max-heap, cu excepția inversării ordinii.

Concluzie

Exemplele date în articol au doar scop explicativ. Puteți modifica declarațiile de mai sus în funcție de cerințele dvs. În acest blog, am aflat despre conceptul de coadă de prioritate în structura de date . Puteți încerca exemplul pentru a vă consolida cunoștințele privind structura datelor.

Dacă sunteți curios să aflați despre știința datelor, consultați programul Executive PG în știința datelor de la IIIT-B și upGrad, care este creat pentru profesioniști care lucrează și oferă peste 10 studii de caz și proiecte, ateliere practice practice, mentorat cu experți din industrie, 1 -on-1 cu mentori din industrie, peste 400 de ore de învățare și asistență profesională cu firme de top.

Învață cursuri de știință a datelor online de la cele mai bune universități din lume. Câștigă programe Executive PG, programe avansate de certificat sau programe de master pentru a-ți accelera cariera.

Care sunt aplicațiile unei cozi de prioritate?

Coada de prioritate este o coadă specială în care elementele sunt inserate pe baza priorității lor. Această caracteristică vine să fie utilă în implementarea diferitelor alte structuri de date. Următoarele sunt câteva dintre cele mai populare aplicații ale cozii de prioritate:
 1. Algoritmul Dijkstra's Shortest Path: Coada de prioritate poate fi utilizată în algoritmul Dijkstra's Shortest Path atunci când graficul este stocat sub forma listei de adiacență.
 2. Algoritmul lui Prim: algoritmul lui Prim folosește coada de prioritate la valorile sau cheile nodurilor și extrage minimul acestor valori la fiecare pas.
 Comprimarea datelor : codurile Huffman folosesc coada de prioritate pentru a comprima datele.
 Sisteme de operare: coada de prioritate este foarte utilă pentru sistemele de operare în diferite procese, cum ar fi echilibrarea încărcăturii și gestionarea întreruperilor.

Ce abordare este folosită în implementarea cozii de prioritate folosind matrice?

Abordarea utilizată în implementarea cozii de prioritate folosind o matrice este simplă. Este creată o structură pentru a stoca valorile și prioritatea elementului și apoi matricea acelei structuri este creată pentru a stoca elementele. În această implementare sunt implicate următoarele operațiuni:
 1. enqueue()-Această funcție inserează elementele la sfârșitul cozii.
 2. peek() - Această funcție va traversa matricea pentru a returna elementul cu cea mai mare prioritate. Dacă găsește două elemente cu aceeași prioritate, returnează elementul cu cea mai mare valoare dintre ele.
 3. dequeue() - Această funcție va muta toate elementele, 1 poziție la stânga elementului returnat de funcția peek() și va micșora dimensiunea.

Care este diferența dintre heap maxim și min heap?

Următoarele ilustrează diferența dintre heap maxim și min-heap.
 Min Heap - Într-un min-heap, cheia nodului rădăcină trebuie să fie mai mică sau egală cu cheile nodului său copil. Utilizează prioritatea crescătoare. Nodul cu cea mai mică cheie este prioritar. Cel mai mic element este afișat înaintea oricărui alt element.
 Max Heap - Într-un heap maxim, cheia nodului rădăcină trebuie să fie mai mare sau egală cu cheia nodurilor sale copii. Utilizează prioritatea descendentă. Nodul cu cea mai mare cheie este prioritar. Cel mai mare element este afișat înaintea oricărui alt element.