Priority Queue is a data structure which maintains a set S of elements with priorities associated with it.Lower the value higher the priority is.
It have broad applications in computer science in engineering ,i.e process scheduling and many graph algorithms .
Priority queues are usually implemented with heap data structure.
Heaps have below 2 properties :
1. Every Element i in the heap will be having at most 2 child’s at index i*2 and i*2+1
2. Every child of the element have higher priority value then the parent.
Heaps provide access to highest priority element in O(1) time . while insertion and deletion are log(N) time operations.
Implementation :
To implement priority queue we can use 2 arrays , one to hold elements while other for priorities.
So, parent of any element can be accessed in constant time by index (i/2) .
And left child can be access in constant time as i*2 for element with index i in array .
Likewise right child can be accessed in constant time as i*2+1 for element with index i in array .
Our priority Queue will provide 3 operations :
1. Insert Elements in Priority Queue in O(long N) time.
2. get minimum element from Priority Queue in O(1) time .
3. get Minimum element and delete it from priority queue in O(log N) time .
Lets Implement these operations in C++
Consider we are given input in the array with priorities as bellow :
input [] = {5,2,10,3,8,1}
And data associated with these priorities are :
data = {5,7,11,18,9,20}
1. Insert Element in priority queue
Consider input is coming from input array as defined earlier.
since initially our queue is empty first element will be inserted as it is
So after inserting 1st element our Priority queue will be :
5
Now consider inserting next element (2) .it will be inserted at left child of 5 , but since it violets heap property (every child of element can have at least priority equal to parent ) here 2<5 , so we will have to swap these two priorities , Our priority queue will look like :
2
/
5
Now consider inserting next element 10 , it place to be inserted is right child of 2 . It doesn’t violets heap property so it will be inserted as it is .
2
/ \
5 10
Now consider inserting next element 3 . It violets heap property since its place in queue is left child of 5 . Here 3<5 , so violating heap property
whenever we will come across any heap violation we will recursively swap elements with parent until no heap violations are there.
Resulting heap will be :
2
/ \
3 10
/
5
Routine used to fix heap property violation :
Heapify_Up(input,i) //Here input is priority array
let j = i/2
if input[i] < input[j] then
swap input[i] and input[j]
Heapify_Up(input,j)
end if
end
end if
end
2. Get minimum element from priority queue
Return root element of heap.
3. Complete implementation of Priority Queue in C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <cstdlib>
#include <cmath>
template <typename T ,typename P >
class priority_queue
{
public:
void insert(T element,P priority)
{
_data.push_back(element);
_priority.push_back(priority);
heapify_up((int)_data.size()-1);
}
T getMin(void);
T extractMin(void);
private:
std::vector<T> _data;
std::vector<P> _priority;
void heapify_up(int index);
void heapify_down(int index);
};
template <typename T ,typename P >
void priority_queue<T,P>::heapify_up(int index)
{
if (index == 0)
{
return;
}
else
{
int j = index/2;
if (_priority[index]<_priority[j])
{
int temp = _data[index]; //Swap Data
_data[index] = _data[j];
_data[j] = temp;
temp = _priority[index]; //Swap Priorities
_priority[index] = _priority[j];
_priority[j] = temp;
heapify_up(j);
}
}
}
template <typename T ,typename P >
void priority_queue<T,P>::heapify_down(int index)
{
size_t len = _data.size()-1;
int j = 0;
if (index*2 > len)
{
return;
}
else if(index*2 <len)
{
int left = index*2;
int right = index*2 +1;
if (_priority[left]<=_priority[right])
{
j = left;
}
else
{
j = right;
}
}
else if(index*2 == len)
{
j = 2*index;
}
if (_priority[j] <_priority[index])
{
int temp = _data[index]; //Swap Data
_data[index] = _data[j];
_data[j] = temp;
temp = _priority[index]; //Swap Priorities
_priority[index] = _priority[j];
_priority[j] = temp;
heapify_down(j);
}
}
template <typename T ,typename P >
T priority_queue<T,P>::getMin(void )
{
return _data[0];
}
template <typename T ,typename P >
T priority_queue<T,P>::extractMin(void )
{
T result = _data[0];
int temp = _data[0];
_data[0] = _data[_data.size()-1];
_data[_data.size()-1] = _data[0];
temp = _priority[0];
_priority[0] = _priority[_priority.size()-1];
_priority[_priority.size()-1] = _priority[0];
_data.pop_back();
_priority.pop_back();
heapify_down(0);
return result;
}
int main(void)
{
priority_queue<int,int> queue;
queue.insert(5, 5);
queue.insert(7, 2);
queue.insert(11, 10);
queue.insert(18, 3);
queue.insert(9, 8);
queue.insert(20, 1);
std::cout<<queue.extractMin();
std::cout<<queue.extractMin();
return 0;
}
No comments :
Post a Comment