Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
coding_cheat_sheet [2020/10/08 00:33] paul [Using Custom Data With Priority Queues] |
coding_cheat_sheet [2021/11/08 00:09] (current) paul [Using Custom Data With Priority Queues] |
||
|---|---|---|---|
| Line 136: | Line 136: | ||
| <code cpp> | <code cpp> | ||
| - | bool sortFunc(const vector< | + | bool compareFunc(const vector< |
| { | { | ||
| return v1[0] < v2[0]; | return v1[0] < v2[0]; | ||
| } | } | ||
| + | |||
| + | // use the sort function by passing in the custom compare fucnction | ||
| + | sort(myVect.begin(), | ||
| </ | </ | ||
| Line 237: | Line 240: | ||
| cout << "Top of min_heap: " << min_heap.top() << endl; | cout << "Top of min_heap: " << min_heap.top() << endl; | ||
| // prints 1 | // prints 1 | ||
| + | </ | ||
| + | ==== Max Heap with Pairs ==== | ||
| + | |||
| + | By default, max heaps using type pair are ordered by the first element. You do not need to create a custom Compare class. See [[https:// | ||
| + | |||
| + | <code cpp> | ||
| + | typedef pair< | ||
| + | |||
| + | priority_queue< | ||
| + | |||
| + | maxHeap.push(make_pair(1, | ||
| + | maxHeap.push(make_pair(2, | ||
| + | |||
| + | // This will be true | ||
| + | assert_true(maxHeap.top().first == 2); | ||
| </ | </ | ||
| ==== Using Custom Data With Priority Queues ==== | ==== Using Custom Data With Priority Queues ==== | ||
| - | There are numerous was of doing this but here is the least verbose | + | There are numerous was of doing this but here is the most elegant |
| + | |||
| + | <code cpp> | ||
| + | struct node{ | ||
| + | node(int id, int value) : id(id), value(value){} | ||
| + | int id; | ||
| + | int value; | ||
| + | }; | ||
| + | |||
| + | auto cmp = [](const node &a, const node &b){ | ||
| + | //Max Heap: | ||
| + | // | ||
| + | //larger b will appear later in the container and therefore have a higher priority | ||
| + | return a.value < b.value; | ||
| + | |||
| + | //MIN Heap: | ||
| + | //if a is larger than b, it will appear before b, so smaller b will have higher priority | ||
| + | return a.value > b.value; | ||
| + | }; | ||
| + | |||
| + | priority_queue< | ||
| + | </ | ||
| + | |||
| + | A less elegant way of overloading the default less than operator is as follows: | ||
| <code cpp> | <code cpp> | ||
| Line 248: | Line 289: | ||
| int id; | int id; | ||
| int value; | int value; | ||
| - | } | + | }; |
| bool operator< | bool operator< | ||
| Line 291: | Line 332: | ||
| }; | }; | ||
| + | // This is a max heap based on number of the int in the pair, and if numbers are the same, word thats lower on the alphabetical compare wins. | ||
| priority_queue< | priority_queue< | ||
| </ | </ | ||