Differences

This shows you the differences between two versions of the page.

--- coding_cheat_sheet [2021/09/28 06:19]
paul [Sorting a 2D Vector]
+++ coding_cheat_sheet [2021/11/08 00:09] (current)
paul [Using Custom Data With Priority Queues]
@@ Line 240: / Line 240: @@
 cout << "Top of min_heap: " << min_heap.top() << endl;
 // prints 1
+</code>
+==== 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://www.geeksforgeeks.org/priority-queue-of-pairs-in-c-ordered-by-first/|here]]
+<code cpp>
+typedef pair<int,int> num_t;
+priority_queue<num_t> maxHeap;
+maxHeap.push(make_pair(1,2));
+maxHeap.push(make_pair(2,2));
+// This will be true
+assert_true(maxHeap.top().first == 2);
 </code>
 ==== Using Custom Data With Priority Queues ====
-There are numerous was of doing this but here is the least verbose way.
+There are numerous was of doing this but here is the most elegant way:
+<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<node, vector<node>, decltype(cmp)> maxHeap(cmp);
+</code>
+A less elegant way of overloading the default less than operator is as follows:
 <code cpp>
@@ Line 251: / Line 289: @@
   int id;
   int value;
-}
+};
 bool operator<(const node& A, const node& B) {