Please enable JavaScript.
Coggle requires JavaScript to display documents.
Priority Queues - Coggle Diagram
Priority Queues
Built -in
C++
priority_queue
python
heapq
Java
PriorityQueue
Implementation
Not that efficient
Unsorted List/array
Extract Max O(n)
Sorted Array/List
Insert O(n)
Efficient
Binary Heap
Insert and Extract max O(logn)
Max heap
Value of parent is always greater or equal to any of its children
Basic operations
Helper operations
Sift Up
Sift Down
Get max
Extract max
Remove
Change priority
min heap
Value of the parent is smaller or equal than any of its children
A binary Tree
What is complete binary tree
How it minimizes the height ??
Two advantages of complete tree
Proving the height logn n is the number of nodes
Store the elements in array
Isnt this creative??
How to maintain the complete binary tree
modify insert and extract max
Insert
Always insert at the end of the array
Extract max
Always replace with the last element of the array
Doubt
Why we call it a heap?
If a binary tree has all values same
Is it both a max and a min heap??
Is there a heap which are not binary ??
m-ary tree
Where might a Priority Queue used ?
Example
List of things to be done and want to start doing the things which are most important and add more items to list
Algorithms that use
Dijkstra
Heap Sort
Huffman algo
Prims algo
Core idea
Collection of elements where we have priority or order among the elements
So you can say give the most priority element
ADT
Operations
Major
Insert
Extract Max priority element
Others
GetMax
Change prioirty
Remove a element
More general that queues