Tiêu đề Priority Queues And Heaps.pdf ✅

Priority Queues & Heaps Topics 1. Introduction to Priority Queues 2. Heaps (Binary Heap) & Implementation details of Heaps 3. Heap Sort & its Implementation 4. Usage details of Heaps in C++, Java & Python 5. Problems & Solutions 6. Important References
Introduction to Priority Queue In computer science, a priority queue is an abstract data type, which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with lower priority. If two elements have the same priority, they are served according to their order in the queue. Queues are a standard mechanism for ordering tasks on a first-come, first-served basis. However, some tasks may be more important or timely than others (higher priority). Priority queues store tasks using a partial ordering based on priority and ensure highest priority task ahead of queue. Heaps are the underlying data structure of priority queues. This underlying heap can be following min heap properties, or max heap properties, depending on the application of the priority queue. Priority Queue primarily supports the following three basic operations: 1. getTop() : Fetching the top priority element. 2. insert() : Insertion of an element. 3. deleteTop() : Deleting the top priority element. Note: Here the top priority element can be a maximum priority or minimum priority element. It totally depends on the implementation of the priority queue. Implementation details of a Priority Queue using different Data Structures We can try and implement priority queue using different data structures. But all the implementations of the priority queue have a major flaw and that has to do with increased Time Complexity. It turns out that Heaps are naturally the best data structure to implement a priority queue, as shown in the following table below: Data Structure getTop() insert() deleteTop() Unordered Array O(N) O(1) O(N) Ordered Array O(1) O(N) O(1) Unordered Linked List O(N) O(1) O(N) Ordered Linked List O(1) O(N) O(1) Balanced Binary Search Tree O(log2(N)) O(log2(N)) O(log2(N)) Binary Heap O(1) O(log2(N)) O(log2(N)) Heap is the maximally efficient implementation, and in fact priority queues are often referred to as "heaps", regardless of how they may be implemented. There are two kind of priority queue: max-priority queue and min-priority queue. Max-heap is used for max-priority queue and Min-heap is used for min-priority queue.
Note: A heap data structure should not be confused with the heap which is a common name for the pool of memory from which dynamically allocated memory is allocated. The term was originally used only for the data structure. Applications of Priority Queue ● Priority Scheduling of Processes in OS ● Dijkstra’s Algorithm for Single Source Shortest Path ● Prim’s Algorithm for Minimum Spanning Tree ● Heap Sort Heaps A heap is a binary tree (in which each node contains a Comparable key value), with two special properties: A. The ORDER property: For every node n, the value in n is greater than or equal to the values in its children (and thus is also greater than or equal to all of the values in its subtrees). This heap is called a max heap because the root node is the maximum. We could also have a min heap where each node’s value is less than or equal to that of its children. Here we will only talk about max heaps, though the same ideas apply to min heaps as well. Using a heap to represent a priority queue, we will always take the root item next as this is the one with the largest priority. Notice that there is no particular relationship between sibling nodes, the only relationship that matters is the parent to the child. B. The SHAPE property (See the image below, and the following properties to understand the Shape property of a heap in a much deeper sense. A heap always follows Complete Binary Tree Property): 1. All leaves are either at depth d or d-1 (for some value d). 2. All of the leaves at depth d-1 are to the right of the leaves at depth d. 3. (a). There is at most 1 node with just 1 child. (b). That child is the left child of its parent, and (c). It is the rightmost leaf at depth d.