if i have to clean the house,play the video games and do my homework ,what would i select to do first?
according to the degree of entertainment ,i would like to play video game first,then i will do my home work and then finally i will clean the house as it is the least entertaining job . As you can see i have given priority to my tasks so that i can do task with maximum priority (according to my criteria) first and then move to other jobs.
computers exactly uses this concept to decide which job among multiple jobs they have to process first or last.
A data structure called priority queue is used to implement this concept.In turn priority queue are implemented with the help of another data structure called heaps(more precisely min heaps or max heaps).
can you be more detailed?
sure why not .i love to be more specific
since priority queues are based on heaps we have two kinds of priority queues
1.MAX PRIORITY QUEUE
minimum number of operations supported are
1.maximum (S) : returns the element of S with largest key
2.Insert (S,x) : insert element into set S.equivalent to S=S U{x}
3.extract max(S) : returns and removes element of S with largest key
4.Increase-Key (S,x,k) : increase the value of element x's key to the new value k note : k>= x 's key
[cpp]
int maximum(int A[]){
return A[1];
}
[/cpp]
independent of input size so
time complexity : O(1) or constant
[cpp]
int extract_maximum(int A[],int *size){
if (*size<1) return ;
int max=A[1];
A[1]=A[*(size)];
max_heapify(A,--(*size));
return max;
}
[/cpp]
time complexity:
Worst case : O(log n);
best case :omega(1)
max_heapify will travel only 1 level down.
[cpp]
void increase_key(int A[],int i,int key){
if (key < A[i]) return ;
while (key > A[i/2] && i>1){
A[i]=A[(i/2)];
i=i/2;
}
A[i]=key;
}
[/cpp]
Time complexity:
worst case : O(log n)
best case : O(1) when i =1
[cpp]
void insert(int A[],int key int &size){
*size=*size+1;
increase_key(A,*size,key);
}
[/cpp]
Time complexity :
worst case : In worst case the increase_key procedure will have to traverse from the child node up to the root thus covering the height of logn. so O(log n)
best case :Best case will occur when the key of the inserted element is less then that of its immediate parent.In this case the increase_key procedure will take only constant time.
so total complexity : omega(1)
0 comments: