Priority Queues
With
Binary Heap using ‘C’
A priority queue is an abstract data type that stores
elements along with their associated priorities. It allows efficient retrieval
of the element with the highest (or lowest) priority. One popular implementation
of a priority queue is using a binary heap.
A binary heap is a complete binary tree that hold the heap property. The heap property specifies that for a max heap, the
priority of any parent node is greater than or equal to the priorities of its
children nodes. In a min heap, the priority of any upper node is less than or
equal to the priorities of its lower nodes.
Here's an overview of how a priority queue with a
binary heap works:
1. Initialization:
·
Create an empty binary heap.
2. Insertion:
·
When inserting an element into the
priority queue, it becomes a new leaf in the binary heap.
·
Place the new element at the next
available position in the tree.
·
Compare the priority of the inserted
element with its parent.
·
If the priority of the parent is
lower (for max heap) or higher (for min heap), swap the elements to maintain
the heap property.
·
Repeat the comparison and swapping
process until the heap property is satisfied.
3. Deletion
(Extraction of the highest priority element):
·
The element with the highest priority
is always located at the root of the binary heap.
·
Remove the root element and replace
it with the last leaf in the heap.
·
Compare the priorities of the new
root with its children.
·
If the priority of the parent is
lower (for max heap) or higher (for min heap) than the priorities of its
children, swap the elements to maintain the heap property.
·
Repeat the comparison and swapping
process with the selected child until the heap property is satisfied.
The insertion and deletion operations maintain the
heap property, ensuring that the element with the highest priority is always at
the root of the binary heap. The time complexity of these operations is O(log
n), where n is the number of elements in the heap.
Binary heaps can be implemented using arrays. The
parent-child relationships of the tree are maintained by the indices of the
elements in the array. For a node at index i, its left child is located at
index 2i+1, and its right child is located at index 2i+2.
Priority queues with binary heaps are commonly used in
various applications that require efficient prioritization, such as scheduling
algorithms, graph algorithms (e.g., Dijkstra's algorithm), and simulation
systems.
Overall, a priority queue with a binary heap provides
a simple and efficient way to manage elements with priorities, allowing fast
access to the highest priority element.
Program:-
#include<stdio.h>
int heap[40];
int size=-1;
int main()
{
int choose;
while(1)
{
printf("enter your choice");
scanf("%d",&choose);
switch(choose)
{
case 1:insert();
break;
case 2:removemax();
break;
case 3:display();
break;
case 4:exit(0);
break;
}
}
}
int insert()
{
int p;
printf("enter element");
scanf("%d",&p);
size=size+1;
heap[size]=p;
moveup(size);
}
int moveup(int i)
{
printf("%d",parent(i));
while(i>0)
{
if(heap[parent(i)]<heap[i])
{
int temp;
temp=heap[parent(i)];
heap[parent(i)]=heap[i];
heap[i]=temp;
}
i=i/2;
}
}
int parent(int i)
{
return (i-1)/2;
}
int lf(int i)
{
return i+1;
}
int rf(int i)
{
return i+2;
}
int display()
{
int
i;
printf("elements in queue is:");
for(i=0;i<=size;i++)
{
printf("%d",heap[i]);
}
}
/*
void delete(int i)
{
heap
//heap[i]=heap[0]+1;
moveup(i);
removemax();
}*/
int removemax()
{
int r=heap[0];
heap[0]=heap[size];
size=size-1;
movedown(0);
}
int movedown(int k)
{
int index=k;
int left=lf(k);
if(left<=size&&heap[left]>heap[index])
{
index=left;
}
int right=rf(k);
if(right<=size&&heap[right]>heap[index])
{
index=right;
}
if(k!=index)
{
int temp;
temp=heap[index];
heap[index]=heap[k];
heap[k]=temp;
movedown(index);
}
}
Output:-
0 Comments