Štruktúra údajov prioritného frontu

V tomto tutoriáli sa dozviete, čo je prioritný front. Dozviete sa tiež o jeho implementáciách v jazykoch Python, Java, C a C ++.

Fronta priority je špeciálny typ frontu, v ktorom je každý prvok spojený s prioritou a je obsluhovaný podľa jeho priority. Ak sa vyskytnú prvky s rovnakou prioritou, zobrazia sa podľa poradia vo fronte.

Všeobecne sa na priradenie priority berie do úvahy hodnota samotného prvku.

Napríklad prvok s najvyššou hodnotou sa považuje za prvok s najvyššou prioritou. V iných prípadoch však môžeme považovať prvok s najnižšou hodnotou za prvok s najvyššou prioritou. V iných prípadoch si môžeme určiť priority podľa našich potrieb.

Odstraňuje sa prvok s najvyššou prioritou

Rozdiel medzi prioritným a normálnym radom

Vo fronte je implementované pravidlo first-in-first-out, zatiaľ čo v prioritnom fronte sú hodnoty odstránené na základe priority . Najskôr sa odstráni prvok s najvyššou prioritou.

Implementácia prioritného frontu

Prioritný front je možné implementovať pomocou poľa, prepojeného zoznamu, haldy dátovej štruktúry alebo binárneho vyhľadávacieho stromu. Medzi týmito dátovými štruktúrami poskytuje halda dátová štruktúra efektívne vykonávanie prioritných frontov.

Preto budeme v tomto výučbe používať štruktúru haldy údajov na implementáciu prioritného frontu. Maximálna hromada, ktorú implementuje, je v nasledujúcich operáciách. Ak sa o tom chcete dozvedieť viac, navštívte max-heap a mean-heap.

Ďalej je uvedená porovnávacia analýza rôznych implementácií prioritného frontu.

Operácie	nakuknúť	vložiť	vymazať
Prepojený zoznam	`O(1)`	`O(n)`	`O(1)`
Binárna halda	`O(1)`	`O(log n)`	`O(log n)`
Binárny vyhľadávací strom	`O(1)`	`O(log n)`	`O(log n)`

Operácie prednostného frontu

Základné operácie prioritného frontu sú vkladanie, odoberanie a prehliadanie prvkov.

Pred preštudovaním prioritného frontu si pozrite štruktúru údajov haldy, aby ste lepšie pochopili binárnu haldu, ktorá sa používa na implementáciu prioritného frontu v tomto článku.

1. Vloženie prvku do prioritného frontu

Vloženie prvku do prioritného frontu (max-heap) sa vykonáva nasledujúcimi krokmi.

Vložte nový prvok na koniec stromu. Vložte prvok na koniec poradia
Heapify strom. Po vložení heapify

Algoritmus pre vloženie prvku do prioritného frontu (max. Hromada)

Ak nie je žiadny uzol, vytvorte nový uzol. else (uzol je už prítomný) vložte newNode na koniec (posledný uzol zľava doprava) heapify pole

Pre Min Heap je vyššie uvedený algoritmus upravený tak, aby parentNodebol vždy menší ako newNode.

2. Vymazanie prvku z prioritného frontu

Odstránenie prvku z prioritného frontu (max-heap) sa vykonáva nasledovne:

Vyberte prvok, ktorý sa má vymazať. Vyberte prvok, ktorý sa má vymazať
Zamieňajte ho s posledným prvkom. Zamieňajte s posledným prvkom uzla listu
Odstráňte posledný prvok. Odstráňte posledný list prvku
Heapify strom. Heapifikujte prioritný front

Algoritmus na odstránenie prvku v prioritnom rade (max. Halda)

 Ak nodeToBeDeleted je leafNode, odstráňte uzol Else swap nodeToBeDeleted s lastLeafNode remove noteToBeDeleted heapify the array

Pre Min Heap je vyššie uvedený algoritmus upravený tak, aby oba childNodesboli menšie ako currentNode.

3. Peeking z prioritného frontu (Nájsť max / min)

Peek operácia vráti maximálny prvok z Max Heap alebo minimálny element z Min Heap bez odstránenia uzla.

Pre haldy Max aj Min Haldy

 návrat rootNode

4. Extrakcia - Max / Min z prioritného frontu

Extract-Max vráti uzol s maximálnou hodnotou po odstránení z Max Heap, zatiaľ čo Extract-Max vráti uzol s minimálnou hodnotou po odstránení z Min Heap.

Implementácia prioritných frontov v Pythone, Jave, C a 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); )