C++

Forum

 
Heap with multiple elements.

tomtran3110 (51)
I'm trying to find a way to make_heap a vector of a struct. And the "key" that I want it to sort with is the price.

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
 
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>

using namespace std;

struct Bid{
  int ID;
  int client;
  int price;
  int share;
};

struct max_h{
  bool operator()(const vector<Bid>& a,const vector<Bid>& b) const{
    return a.price<b.price;
  }
};

struct min_h{
  bool operator()(const vector<Bid>& a,const vector<Bid>& b) const{
    return a.price>b.price;
  }
};

void print_heap(vector<Bid>& buyer){
  //print
}

main(){
  ifstream infile("file.txt");

  vector<Bid> buyer;
  vector<Bid> seller;
  int buyerID;
  
  if(infile.is_open()){
    string line;
    int index, client, action, price, share_count;
    while(getline(infile, line)){
      stringstream get(line);
      get >> index >> client >> action >> price >> share_count;
      Bid A;
      A.ID = index;
      A.client = client;
      A.price = price;
      A.share = share_count;
      if(action == 0){
        buyer.push_back(A);
        make_heap(buyer.begin(), buyer.end(), max_h());
      }
      else if(action == 1){
        seller.push_back(A);
        make_heap(seller.begin(), seller.end(), min_h());
      }
      else if(action == 2){
        //find and remove then upheap/downheap
      }
    }
  }
}


[Error] 'const class std::vector<Bid>' has no member named 'price'
Last edited on
tipaye (535)
Consider 
1
2
3
4
5
 
struct max_h{
  bool operator()(const vector<Bid>& a,const vector<Bid>& b) const{
    return a.price<b.price;
  }
};


Bid has a member named price
std::vector does not.

I think you probably meant:
1
2
3
4
5
 
struct max_h{
  bool operator()(const Bid& a,const Bid& b) const{
    return a.price<b.price;
  }
};


Same goes for min_h.
Suggest using a lambda function, save you a lot of typing and brow wrinkling
tomtran3110 (51)
This is the first time I hear lambda function. And since deadline is close I would like to finish my code before trying anything new. You help me with my heap construction. But once again, since this make my heap to construct with the price as key, I miss which index come first go first... Can I have a heap with 2 keys? Sorting with price first and if encounter the same price then the smaller index should come before bigger one. Something like this: (BTW, I change my input to standard input and use I/O redirection since the specs ask me to)

input file:
1
2
3
4
5
6
 
0	973	0	160	91
1	155	0	188	50
2	903	0	160	55
3	178	1	186	5
4	54	0	117	91
5	804	1	128	67


my code:
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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>

using namespace std;

struct Bid{
  int bidID;
  int client;
  int price;
  int share;
};

struct max_h{
  bool operator()(const Bid& a,const Bid& b) const{    //construct max heap with price as key
    return a.price<b.price;
  }
};

struct min_h{
  bool operator()(const Bid& a,const Bid& b) const{    //construct min heap with price as key
    return a.price>b.price;
  }
};

void print_heap(vector<Bid>& heap){  //checking heap content
  for(int i=0; i<heap.size(); ++i){
    cout<< heap.at(i).client << " ";
  }
  return;
}

void print_trans(vector<Bid>& buyer, vector<Bid>& seller, int&  transactionID){
  if(buyer.empty() || seller.empty())
    return;
  if(buyer.at(0).price < seller.at(0).price)
    return;
    
  if(buyer.at(0).share > seller.at(0).share){
    cout << transactionID << "\t" << buyer.at(0).client << "\t" << seller.at(0).client << "\t" << seller.at(0).price << "\t" << seller.at(0).share << endl;
    
    buyer.at(0).share -= seller.at(0).share;
    transactionID++;
    
    pop_heap(seller.begin(), seller.end(), min_h());
    seller.pop_back();
    
    print_trans(buyer, seller, transactionID);
  }
  else if(buyer.at(0).share < seller.at(0).share){
    cout << transactionID << "\t" << buyer.at(0).client << "\t" << seller.at(0).client << "\t" << seller.at(0).price << "\t" << buyer.at(0).share << endl;
    
    seller.at(0).share -= buyer.at(0).share;
    transactionID++;
    
    pop_heap(buyer.begin(), buyer.end(), max_h());
    buyer.pop_back();
    
    print_trans(buyer, seller, transactionID);
  }
  else{
    cout << transactionID << "\t" << buyer.at(0).client << "\t" << seller.at(0).client << "\t" << seller.at(0).price << "\t" << seller.at(0).share << endl;
    
    transactionID++;
    
    pop_heap(seller.begin(), seller.end(), min_h());
    seller.pop_back();
    pop_heap(buyer.begin(), buyer.end(), max_h());
    buyer.pop_back();
    
    print_trans(buyer, seller, transactionID);
  }
  
  return;
}

main(){
  vector<Bid> buyer;
  vector<Bid> seller;
  
  string line;
  int index, client, action, price, share_count;
  int transactionID=0;
  while(getline(cin, line)){
    stringstream get(line);
    get >> index >> client >> action >> price >> share_count;
    Bid A;
    A.bidID = index;
    A.client = client;
    A.price = price;
    A.share = share_count;
    if(action == 0){
      buyer.push_back(A);
      make_heap(buyer.begin(), buyer.end(), max_h());
      if(!seller.empty()){
        if(buyer.at(0).price >= seller.at(0).price){    //check for available transaction. If there is, print.
          print_trans(buyer, seller, transactionID);
        }
      }
    }
    else if(action == 1){
      seller.push_back(A);
      make_heap(seller.begin(), seller.end(), min_h());
      if(!buyer.empty()){
        if(buyer.at(0).price >= seller.at(0).price){    //check for available transaction. If there is, print.
          print_trans(buyer, seller, transactionID);
        }
      }
    }
    else if(action == 2){
      for(int i=0; i<buyer.size(); ++i){
        if(buyer.at(i).bidID == index){
          buyer.erase(buyer.begin()+i);
          make_heap(buyer.begin(), buyer.end(), max_h());
        }
      }
      for(int i=0; i<seller.size(); ++i){
        if(seller.at(i).bidID == index){
          seller.erase(seller.begin()+i);
          make_heap(seller.begin(), seller.end(), min_h());
        }
      }
    }
  }
}


my output:
1
2
3
 
0	155	178	186	5
1	155	804	128	45
2	903	804	128	22


expected output:
1
2
3
 
0	155	178	186	5
1	155	804	128	45
2	973	804	128	22


BTW, I haven't check if action == 2 yet. So you can skip that.
Last edited on
tomtran3110 (51)
I think I should get some change with max_h() and min_h(). But I just don't know...
tipaye (535)
According to what you said above you want the following situation:

Input file:
1
2
3
4
 
0	973	0	160	91
1	155	0	188	50
2	903	0	160	55
4	54	0	117	91

after sorting using max_h as less than operator:
1
2
3
4
 
1	155	0	188	50
0	973	0	160	91
2	903	0	160	55
4	54	0	117	91

If that's the case then you can do max_h and min_h like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
struct max_h{
  bool operator()(const Bid& a,const Bid& b) const{    //construct max heap with price as key
  
	if (a.price == b.price)
		return a.bidID > b.bidID;
    return a.price<b.price;
  }
};

struct min_h{
  bool operator()(const Bid& a,const Bid& b) const{    //construct min heap with price as key
	if (a.price == b.price)
		return a.bidID < b.bidID;
    return a.price>b.price;
  }
};
Last edited on
tomtran3110 (51)
Actually, it's

1
2
 
if(a.price == b.price)
  return a.bidID > b.bidID;


for both cases since bidID must be from small to large in anycase. Thanks!
Last edited on
Topic archived. No new replies allowed.