Making a function that counts number of elements in PriorityQueue in C

Question

TASK:

I am working on a homework for my Structure and Algorithms college class. The task is to implement Priority Queue in C using the heap and form the main so it can support operations such as:

INSERT s (inserts string s in a Priority Queue)
DELETE (deletes the element with the lowest priority)
NUMBER (returns number of elements in a Priority Queue)

We should also print out preorder of the Priority Queue every time we write an operation in the main. We can assume that the heap is implemented with the pointers. So I implemented it in structure that looks like this:

typedef char* elementtype;

typedef struct celltag {
    elementtype zapis;
    struct celltag *left, *right, *parent;
}   celltype;

typedef celltype* node;
typedef celltype* PriorityQueue;

I also implemented following functions:

void PrMakeNull(PriorityQueue *Ap)
int PrEmpty(PriorityQueue A)
void PrInsert(elementtype x, PriorityQueue *Ap)
elementtype PrDeleteMin(PriorityQueue *Ap)
void Preorder(PriorityQueue A)

QUESTION:
I should implement "number function" with the header like this:

int Number(PriorityQueue P)

The function should not change the Priority Queue A after calling Number(A). Also, the function should be independent on Priority Queue implementation. (I think that means I should only use PrMakeNull, PrEmpty, PrInsert, PrDeleteMin). Is that even possible? How could I do it? How should it look like?

WHAT HAVE I TRIED:
1)

//This one is independent on Priority Queue implementation but destroys the Priority Queue. 
int Number(PriorityQueue P){
    PriorityQueue S;
    PrMakeNull(&S);
    int counter=0;
    while(!PrEmpty(P))
    {
        PrInsert(PrDeleteMin(&P), &S);
        counter++;
    }
    while(!PrEmpty(S))
    {
        PrInsert(PrDeleteMin(&S), &P);
    }
    return counter;
}

2)

//This one is dependent on Priority Queue implementation but doesn't destroy the Priority Queue. 
int Number(PriorityQueue A){
    int returning_number=1;
    if (A == NULL)
        return 0;
    if(A->left!=NULL)
        returning_number+=Number(A->left);
    if(A->right!=NULL)
        returning_number+=Number(A->right);
    return returning_number;
}

*"I think that means ..."* - Then you should probably ask your teacher. — klutt, Jan 21 '20 at 11:28
Shouldn't he need to give me the solution to the half homework then? I think I will have to do that... — Tin Sertić, Jan 21 '20 at 11:34
You may want to read this. Don't hide structs and pointers with typedefs. https://stackoverflow.com/a/54752982/6699433 — klutt, Jan 21 '20 at 11:42
It's Priority Queue implemented through the heap(sort of Binary Tree) — Tin Sertić, Jan 21 '20 at 12:36
I'd suggest having a top-level struct called `PriorityQueue` that contains the number of nodes (`count`), and a pointer to the root node. Increment `count` when you insert an item, and decrease `count` when you remove an item. A `Number` function that traverses the tree is O(n), which will kill your performance when you have a large number of items in the queue. — Jim Mischel, Jan 24 '20 at 23:00
Also, are you sure that "using the heap" means that you're supposed to create a pointer-based priority queue? Is it possible that you're supposed to implement a [binary heap](https://en.wikipedia.org/wiki/Binary_heap) priority queue? — Jim Mischel, Jan 24 '20 at 23:03

Zig Razor · Accepted Answer · 2020-01-21T12:04:49.983

2

You can solve this with a recursive algorithm that does not depend on function you list. The code could be like this :

int Number(PriorityQueue A)
{
    if(!A) return 0;

    return 1 + Number(A->left) + Number(A->right);
}

This is the best way to solve this for my opinion.

if you have some trouble on recursion i leave you a useful link:

recursion

Edit:

I don't think there is a possible to abstract from the struct of priority queue this because the implementation of PrEmpty, PrInsert, PrDeleteMin, and Preorder already depends on the struct of priority queue. So why search for an implementation that depends only on these function? Also to be generic you can define another function that search for an element without delete them and implement it at the same level of the above function, or better a simple iterator over the priority queue.

edited Jan 21 '20 at 12:04

answered Jan 21 '20 at 11:37

Zig Razor

3,381
2
15
35

I understand the recursion you wrote. That's the shorter version of my 2) code. But the same function should also work if you implement Priority Queue like this(Function should be independent on implementation): typedef struct{ elementtype elements[MAXSIZE] ; int last; }PriorityQueue; – Tin Sertić Jan 21 '20 at 11:44
It looks also silly to me to search for an implementation that depends only on these functions! But I think that's the task. Those function are the functions that characterise Priority Queue in our book. Last time, my friend used implementation specific notation and got only 4/8 points. – Tin Sertić Jan 21 '20 at 12:11
1

Yes but i suggest you to ask your professor if your solution 1 is ok or if you can create new auxiliary functions – Zig Razor Jan 21 '20 at 13:21
I asked my asistent if the function you presented is good enough. – Tin Sertić Jan 21 '20 at 19:36
1

Thank you so much... please accept the answer if correct – Zig Razor Jan 21 '20 at 23:48
Thank you, I will make it as you presented it, but I made PrRightChild and PrLeftChild function (as my roommate told me) (and replaced A->left with PrLeftChild(A) and replaced A->right with PrRightChild(A)) so the function can work on Priority Queue implemented through heap (now the function can work if the heap is implemented both on pointers and array) – Tin Sertić Jan 22 '20 at 06:15

score 0 · Answer 2 · answered Jan 21 '20 at 11:48

0

int Number(PriorityQueue A) {
    if(PrEmpty(A)) return 0;
    elementType val = PrDeleteMin(&A);
    int num = 1 + Number(A);
    PrInsert(val, &A);
    return num;

}

answered Jan 21 '20 at 11:48

Vengatesh Subramaniyan

883
8
7

1

this solution destroy your queue as you do in you option 1 code. the PrDeleteMin(&A) return a copy of elementType and delete the element from the queue so the A is destoyed and then rebuilded, as you do in code 1 – Zig Razor Jan 21 '20 at 11:58
It changes the PriorityQueue. – Tin Sertić Jan 21 '20 at 12:13

Making a function that counts number of elements in PriorityQueue in C

2 Answers2