C++

Forum

 
Priority Queue with heap input string and int

TomRyan12 (4)
I got a Priority Queue implemented using heap with integers but i would now like to add a string with it. I can't find any thing to help me or understand on how to approach this

So basically i add an integer by

pq.Enqueue(newNumber)
But would like to also add string to that and that person would be attached to that number.

pq.Enqueue(newNumber, newPerson)
This is my header file queue and heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
 
template<class ItemType>
struct HeapType
{
    void ReheapDown(int root, int bottom);
    void ReheapUp(int root, int bottom);
    void Swap(ItemType& one, ItemType& two);
    ItemType* elements;                         
    int numElements;
};


template<class ItemType>
class PQType

{
public:
    PQType(int);  
    ~PQType();      
    void Enqueue(ItemType newItem);
    void Dequeue(ItemType& item);    
private:
    int numItems;
    HeapType<ItemType> items;
    int maxItems;  
};

template<class ItemType>
PQType<ItemType>::PQType(int max)
{
    maxItems = max;
    items.elements = new ItemType[max];
    numItems = 0;
}

template<class ItemType>
PQType<ItemType>::~PQType()
{
    delete[] items.elements;
}

template<class ItemType>
void PQType<ItemType>::Enqueue(ItemType newItem)
// Post: newItem is in the queue.
{
    numItems++;
    items.elements[numItems - 1] = newItem;
    items.ReheapUp(0, numItems - 1);
}

template<class ItemType>
void PQType<ItemType>::Dequeue(ItemType& item)
{
    item = items.elements[0];
    items.elements[0] = items.elements[numItems - 1];
    numItems--;
    items.ReheapDown(0, numItems - 1);
}

template <class ItemType>
void HeapType<ItemType>::Swap(ItemType& one, ItemType& two)
{
    ItemType temp;
    temp = one;
    one = two;
    two = temp;
}

template<class ItemType>
void HeapType<ItemType>::ReheapUp(int root, int bottom)
// Post: Heap property is restored.
{
    int parent;

    if (bottom > root)
    {
        parent = (bottom - 1) / 2;
        if (elements[parent] < elements[bottom])
        {
            Swap(elements[parent], elements[bottom]);
            ReheapUp(root, parent);
        }
    }
}
template<class ItemType>
void HeapType<ItemType>::ReheapDown(int root, int bottom)
// Post: Heap property is restored.
{
    int maxChild;
    int rightChild;
    int leftChild;

    leftChild = root * 2 + 1;
    rightChild = root * 2 + 2;
    if (leftChild <= bottom)
    {
        if (leftChild == bottom)
            maxChild = leftChild;
        else
        {
            if (elements[leftChild] <= elements[rightChild])
                maxChild = rightChild;
            else
                maxChild = leftChild;
        }
        if (elements[root] < elements[maxChild])
        {
            Swap(elements[root], elements[maxChild]);
            ReheapDown(maxChild, bottom);
        }
    }
}
ne555 (10692)
1
2
3
4
5
6
7
 
struct Person{
   int id;
   std::string name;
   bool operator<(const Person &b) const; //or whatever you use for comparison in your functions
};

HeapType<Person> pq;
TomRyan12 (4)
Do i declare this in main or in my header file? Also i don't use any function to compare
Topic archived. No new replies allowed.