Exercise 1: Create a priority queue of characters by implementing min-heap data
ID: 3548572 • Letter: E
Question
Exercise 1:
Create a priority queue of characters by implementing min-heap data structure. Provide a menu then test insert, findmin, removeMin, and display function. Sample output is as follows.
Algorithm: InsertItem(v)
add v as next leaf
while v<parent(v) {
swapElements(v,parent(v))
v=parent(v)
}
Algorithm: RemoveMin()
temp = value of root
swap root value with last leaf
delete last leaf
v = root
while v > any child(v) {
swapElements(v, smaller child(v))
v= smaller child(v)
}
return temp
Sample output:
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: d
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: e
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: a
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: c
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
1
Enter data: b
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
4
the elements in the priority queue are:
a b d e c
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
3
Minimum char is: a
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
2
a is deleted
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
4
the elements in the priority queue are:
b c d e
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
3
Minimum char is: b
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
2
b is deleted
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
4
the elements in the priority queue are:
c e d
Options:
1.insert 2.delete min 3.findmin 4.display 5.exit
5
Press any key to continue . . .
References:
Create a priority queue of characters by implementing min-heap data structure. Provide a menu then test insert, find min, remove Min, and display function. Sample output is as follows.Explanation / Answer
// MIN-HEAP
#include<stdio.h>
char heap[10000];
int heapsize = 0;
/*Insert an element into the heap */
void insertItem(char v)
{
int i;
char temp;
heapsize++;
heap[heapsize] = v;
i = heapsize;
while(i > 1)
{
if ( heap[i/2] <= heap[i])
break;
//swapping
temp = heap[i];
heap[i] = heap[i/2];
heap[i/2] = temp;
i/=2;
}
}
/* heap[1] is the minimum element. So we remove heap[1]. Size of the heap is decreased.
Now heap[1] has to be filled. We put the last element in its place and see if it fits.
If it does not fit, take minimum element among both its children and replaces parent with it.
Again See if the last element fits in that place.*/
char deleteMin(void)
{
char minElement,lastElement;
int now,minIdx;
minElement = heap[1];
lastElement = heap[heapsize--];
for(now = 1; now*2 <= heapsize ;now = minIdx)
{
/*minIdx is the minimum among both of now's children*/
minIdx = now*2;
if(minIdx != heapsize && heap[minIdx+1] < heap[minIdx] )
{
minIdx++;
}
/* To check if the last element fits ot not it suffices to check if the last element
is less than the minimum element among both the children*/
if(lastElement > heap[minIdx])
{
heap[now] = heap[minIdx];
}
else /* It fits there */
{
break;
}
}
heap[now] = lastElement;
return minElement;
}
int main()
{
int response,i;
char data,temp;
while(1)
{
printf("Options: 1.insert 2.delete min 3.findmin 4.display 5.exit ");
scanf("%d",&response);
scanf("%c",&temp);
switch(response)
{
case 1://insert
printf("Enter data:");
scanf("%c",&data);
insertItem(data);
break;
case 2://delete minimum
printf("%c is deleted. ",deleteMin());
break;
case 3://find minimum
printf("Minimum char is %c ",heap[1]);
break;
case 4://dispaly
for(i=1;i<=heapsize;i++)
{
printf("%c ",heap[i]);
}
printf(" ");
break;
case 5:
return 0;
}
}
}
SourceCode: http://kopasite.net/up/dbb71g8zsjwp5ig/minHeap.c
References:http://en.wikibooks.org/wiki/Data_Structures/Min_and_Max_Heaps
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.