У овом упутству ћете научити шта је приоритетни ред. Такође ћете научити о њеним имплементацијама у Питхон, Јава, Ц и Ц ++.
Приоритетни ред је посебна врста реда у којем је сваки елемент повезан са приоритетом и служи се према свом приоритету. Ако се појаве елементи са истим приоритетом, они се сервирају према њиховом редоследу у реду.
Генерално се за додељивање приоритета узима у обзир вредност самог елемента.
На пример, елемент са највећом вредношћу сматра се елементом највишег приоритета. Међутим, у другим случајевима можемо узети елемент са најмањом вредношћу као елемент највишег приоритета. У другим случајевима можемо поставити приоритете у складу са својим потребама.
Уклањање елемента највишег приоритета
Разлика између реда приоритета и нормалног реда
У реду се примењује правило први у првом, док се у приоритетном реду вредности уклањају на основу приоритета . Прво се уклања елемент са највишим приоритетом.
Примена реда приоритета
Редослед приоритета може се имплементирати помоћу низа, повезане листе, структуре података гомиле или бинарног стабла претраживања. Међу овим структурама података, структура података гомиле пружа ефикасну примену приоритетних редова.
Стога ћемо користити структуру података гомиле за примену реда приоритета у овом упутству. Мак-хеап је имплементиран у следећим операцијама. Ако желите да сазнате више о томе, посетите мак-хеап и меан-хеап.
Упоредна анализа различитих примена приоритетног реда дата је у наставку.
| Операције | завирити | уметак | избрисати |
|---|---|---|---|
| Повезана листа | O(1) | O(n) | O(1) |
| Бинарна гомила | O(1) | O(log n) | O(log n) |
| Бинарно стабло претраживања | O(1) | O(log n) | O(log n) |
Операције приоритетног реда
Основне операције реда приоритета су уметање, уклањање и провиривање елемената.
Пре проучавања реда приоритета, погледајте структуру података гомиле ради бољег разумевања бинарне гомиле која се користи за примену реда приоритета у овом чланку.
1. Уметање елемента у приоритетни ред
Уметање елемента у приоритетни ред (мак-хеап) врши се следећим корацима.
- Уметните нови елемент на крај стабла.
Уметните елемент на крај реда - Ојачајте дрво.
Ојачати након уметања
Алгоритам за уметање елемента у приоритетни ред (мак-хеап)
Ако нема чвор, креирајте нови чвор. иначе (чвор је већ присутан) убаците новиЧвор на крају (последњи чвор слева удесно.) хеапифи низ
За Мин Хеап, горњи алгоритам је модификован тако да parentNodeје увек мањи од newNode.
2. Брисање елемента из реда приоритета
Брисање елемента из реда приоритета (мак-хеап) врши се на следећи начин:
- Изаберите елемент који желите избрисати.
Изаберите елемент који желите избрисати - Замените га последњим елементом.
Замените са последњим елементом чвора листа - Уклоните последњи елемент.
Уклоните задњи лист елемента - Ојачајте дрво.
Ојачајте приоритетни ред
Алгоритам за брисање елемента у приоритетном реду (мак-хеап)
Ако је нодеТоБеДелетед леафНоде, уклоните чвор Елсе замијените нодеТоБеДелетед са ластЛеафНоде уклоните нотеТоБеДелетед, појачава низ
За Мин Хеап, горњи алгоритам је модификован тако да су оба childNodesмања од currentNode.
3. Провиривање из приоритетног реда (пронађи макс. / Мин.)
Пеек операција враћа максимални елемент из Мак Хеап или минимални елемент из Мин Хеап без брисања чвора.
И за Мак хеап и Мин Хеап
ретурн роотНоде
4. Издвоји макс. / Мин. Из реда приоритета
Ектрацт-Мак враћа чвор с максималном вриједношћу након уклањања из Мак Хеап док Ектрацт-Мин враћа чвор с минималном вриједношћу након уклањања из Мин Хеап.
Имплементације приоритетног реда у Питхон, Јава, Ц и Ц ++
Питхон Јава Ц Ц ++ # 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); )
Апликације за приоритетни ред
Неке од апликација из приоритетног реда су:
- Дијкстрин алгоритам
- за примену стека
- за уравнотежење оптерећења и руковање прекидима у оперативном систему
- за компресију података у Хуффмановом коду
