U ovom vodiču naučit ćete što je prioritetni red. Također, naučit ćete o njezinim implementacijama u Pythonu, Javi, C i C ++.
Prioritetni red je posebna vrsta reda u kojem je svaki element povezan s prioritetom i poslužuje se prema svom prioritetu. Ako se pojave elementi s istim prioritetom, oni se poslužuju prema redoslijedu u redu čekanja.
Općenito se za dodjeljivanje prioriteta uzima u obzir vrijednost samog elementa.
Na primjer, Element s najvećom vrijednošću smatra se elementom najvišeg prioriteta. Međutim, u drugim slučajevima možemo uzeti element s najmanjom vrijednošću kao element najvišeg prioriteta. U drugim slučajevima možemo postaviti prioritete prema svojim potrebama.
Uklanjanje elementa najvišeg prioriteta
Razlika između reda prioriteta i uobičajenog reda čekanja
U redu čekanja implementira se pravilo prvi u prvom, dok se u prioritetnom redu vrijednosti uklanjaju na temelju prioriteta . Prvo se uklanja element s najvišim prioritetom.
Provedba reda prioriteta
Prioritetni red može se implementirati pomoću niza, povezanog popisa, strukture podataka hrpe ili binarnog stabla pretraživanja. Među tim strukturama podataka, struktura podataka hrpe omogućuje učinkovitu implementaciju prioritetnih redova.
Stoga ćemo koristiti strukturu podataka hrpe za implementaciju reda prioriteta u ovom vodiču. Max-heap je implementiran u sljedećim operacijama. Ako želite saznati više o tome, posjetite max-heap i mean-heap.
U nastavku je dana usporedna analiza različitih implementacija reda prioriteta.
| Operacije | zaviriti | umetnuti | izbrisati |
|---|---|---|---|
| Povezani popis | O(1) | O(n) | O(1) |
| Binarna hrpa | O(1) | O(log n) | O(log n) |
| Binarno stablo pretraživanja | O(1) | O(log n) | O(log n) |
Operacije s prioritetnim redom
Osnovne operacije reda prioriteta su umetanje, uklanjanje i zavirivanje elemenata.
Prije proučavanja reda prioriteta, pogledajte strukturu podataka hrpe radi boljeg razumijevanja binarne hrpe jer se koristi za implementaciju reda prioriteta u ovom članku.
1. Umetanje elementa u prioritetni red
Umetanje elementa u prioritetni red (max-heap) vrši se sljedećim koracima.
- Umetnite novi element na kraj stabla.
Umetnite element na kraj reda - Ojačajte stablo.
Ojačati nakon umetanja
Algoritam za umetanje elementa u red prioriteta (max-heap)
Ako nema čvora, stvorite novi čvor. inače (čvor je već prisutan) umetnite newNode na kraj (zadnji čvor slijeva udesno.) heapify niz
Za Min Heap, gornji algoritam je izmijenjen tako da parentNodeje uvijek manji od newNode.
2. Brisanje elementa iz reda prioriteta
Brisanje elementa iz reda prioriteta (max-heap) vrši se na sljedeći način:
- Odaberite element koji želite izbrisati.
Odaberite element koji želite izbrisati - Zamijenite ga posljednjim elementom.
Zamijenite s posljednjim elementom čvora lista - Uklonite posljednji element.
Uklonite zadnji list elementa - Ojačajte stablo.
Pojačajte prioritetni red
Algoritam za brisanje elementa u redu prioriteta (max-heap)
Ako je nodeToBeDeleted leafNode, uklonite čvor Inače zamijenite nodeToBeDeleted s lastLeafNode uklonite noteToBeDeleted pojačava niz
Za Min Heap, gornji algoritam je izmijenjen tako da su oba childNodesmanja od currentNode.
3. Zavirivanje iz prioritetnog reda (pronađi maks. / Min)
Peek operacija vraća maksimalni element iz Max Heap ili minimalni element iz Min Heap bez brisanja čvora.
I za Max heap i Min Heap
vrati rootNode
4. Izdvoji-Max / Min iz reda prioriteta
Extract-Max vraća čvor s maksimalnom vrijednošću nakon uklanjanja iz Max Heap, dok Extract-Min vraća čvor s minimalnom vrijednošću nakon uklanjanja iz Min Heap.
Implementacije prioritetnog reda u Pythonu, Javi, C i C ++
Python Java C C ++ # Priority Queue implementation in Python # Function to heapify the tree def heapify(arr, n, i): # Find the largest among root, left child and right child largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # Swap and continue heapifying if root is not largest if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) # Function to insert an element into the tree def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum) for i in range((size // 2) - 1, -1, -1): heapify(array, size, i) # Function to delete an element from the tree def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size - 1) = array(size - 1), array(i) array.remove(size - 1) for i in range((len(array) // 2) - 1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr))
// Priority Queue implementation in Java import java.util.ArrayList; class Heap ( // Function to heapify the tree void heapify(ArrayList hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) // Print the tree void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) // Driver code public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
// Priority Queue implementation in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) // Function to insert an element into the tree void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) // Function to delete an element from the tree void deleteRoot(int array(), int num) ( int i; for (i = 0; i = 0; i--) ( heapify(array, size, i); ) ) // Print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) // Driver code int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); )
// Priority Queue implementation in C++ #include #include using namespace std; // Function to swap position of two elements void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(vector &hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; i--) ( heapify(hT, i); ) ) // Print the tree void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) // Driver code int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )
Prijave s prioritetnim redom
Neke od aplikacija prioritetnog reda su:
- Dijkstrin algoritam
- za implementaciju stoga
- za uravnoteženje opterećenja i rukovanje prekidima u operacijskom sustavu
- za kompresiju podataka u Huffmanovom kodu
