Priority queue and overloaded operators

1 priority queue

1.1 Heap

The underlying implementation of the priority queue is the heap.

The heap must be a complete binary tree. Heaps are divided into two types: large root heaps and small root heaps. For a heap, only the top of the heap (root node) is meaningful, so the heap has only two operations: put (up) and delete (down), and the deleted objects can only Could be the top of the pile.

Take Dagendui as an example:

The characteristic of a large root heap is that for each node, its child node must be smaller than its parent node. Therefore, the top of the big root heap must be the largest of all elements.

Put (up): Since the heap must be a complete binary tree, put the inserted element into the first free position from left to right at the last level of the heap, and then check whether the large root heap at this time meets its characteristics. (That is, after adding this element, whether its parent node is larger than it), if not, exchange the values of the parent node and this element. Repeat the above operations until the element reaches the top of the heap or meets the conditions.
Delete (down): Delete the top of the heap, move the last element of the last layer from left to right to the root node position, and then check whether the large root heap at this time meets its characteristics (that is, after adding this element, Whether its son node is smaller than it), if not, select the son node with a larger value to exchange the value of this element. Repeat the above operations until the element reaches the bottom of the heap or until the conditions are met.

The same is true for small root heaps, which is the opposite of large root heaps:

The characteristic of the small root heap is that for each node, its child node must be larger than its parent node. Therefore, the top of the big root heap must be the smallest one among all elements.

Put (up): Maintenance condition The parent node must be smaller than the element. If it is not met, exchange the value of the parent node and this element.
Delete (down): Maintenance condition The element must be smaller than the child node. If it is not met, exchange the child node with a smaller value and the value of this element.

1.2 Priority queue priority_queue

Priority queue priority_queue, a queue that is automatically sorted according to priority, is a type of STL container. The underlying implementation of the priority queue is the heap. Similar to the heap, the priority queue is also divided into two types.

Header file: #include

Operation	Meaning
`priority_queue q`	Define a large root heap of int data type
`priority_queue, greater > q`	Define a small root heap of int data type
`q.push(i)`	Put element i
`q.pop()`	Delete the top element of the heap
`q.top()`	Return the value of the top element of the heap
`q.empty()`	Determine whether it is empty and return bool type
`q.size()`	Returns the number of elements

2 Overloaded operators

2.1 Overloaded operators

Overloading operators is a function syntax that redefines and loads operators and gives them different meanings. Usually used for operations and comparisons of structures.

Example:

struct node{<!-- -->
int key, val;
bool operator<(const node & amp; x) const {<!-- -->
//Overload the operator <, the logical operation returns the bool type, the parameter is x, and the other parameter is the current structure
return key < x.key;
//For node type variables <defined as node with smaller key <node with larger key
}
};

2.2 Constructor

Function syntax for fast assignment to structures.

Example:

struct node{<!-- -->
int key, val;
node(int x, int y) {<!-- --> //The function type is the structure name
key = x;
val = y;
//The parameter x is assigned to key, and y is assigned to val
}
};

Such structures can be assigned values after the constructor:

node n(1024, 2048);
node m = {<!-- -->First, Second};

2.3 Examples

2.3.1 Luogu P1631 sequence merging

[Title link]

Title description
There are two lengths

Themonotonenon-decreasing sequence of N

A,B

A, B, in

A,B

Take one number from A and B and add them together to get

N^2

N2 sums, find this

N^2

The smallest of N2 sums

N number.

Input format
The first line is a positive integer

N;
second line

N integers

…

A_{1\dots N}

A1…N?.
The third row

N integers

…

B_{1\dots N}

B1…N?.

Output format
one line

N integers, from small to large, represent this

N smallest sums.

Sample

Sample input

3
2 6 6
1 4 8

Sample output

3 6 7

Tips
for

50\%

50% of the data,

≤

N \le 10^3

N≤103.
for

100

100\%

100% data,

≤

1 \le N \le 10^5

1≤N≤105,

≤

1 \le a_i,b_i \le 10^9

1≤ai?,bi?≤109.

2.3.2 Idea 1

enumeration

N^2

N2 combination solutions. The time complexity is

(

)

O(n^2)

O(n2).

Method to reduce time complexity: Right

A and

B Sort in ascending order.

Number of elements in the priority queue
< n a[i] + a[j].
Number of elements in the priority queue
≥

n

≥n

≥n: If the top element of the heap is less than a[i] + a[j], delete the top element of the heap and put it into a[i] + a[j]; if not less than, because

A

i

+

B

j

< A i + B j … n A_i + B_j

AC code:

#include <bits/stdc + + .h>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int n;
ll a[N], b[N], c[N];
priority_queue<ll> q; //Priority queue
int main() {<!-- -->
cin >> n;
    for (int i = 1; i <= n; i + + ) cin >> a[i];
    for (int j = 1; j <= n; j + + ) cin >> b[j];
    sort(a + 1, a + n + 1); //Sort
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i + + ) {<!-- -->
    for (int j = 1; j <= n; j + + ) {<!-- -->
    if (q.size() < n) {<!-- --> //There are less than n elements, put in
    q.push(a[i] + b[j]);
} else {<!-- -->
if (a[i] + b[j] < q.top()) {<!-- --> //a[i] + a[j] is smaller, replace the larger value in the queue
q.pop();
q.push(a[i] + b[j]);
} else {<!-- -->
break; //The subsequent results will inevitably become larger and larger, ending the loop
}
}
}
}
for (int i = n; i >= 1; i--) {<!-- -->
c[i] = q.top();
q.pop();
}
for (int i = 1; i <= n; i + + ) cout << c[i] << " ";
return 0;
}

2.3.3 Idea 2

Define a structure containing three values:

x

x

x, in order

A

A

A number in the sequence
y

y

y, in order

B

B

Number in sequence B
v

a

l

val

val,

A

x

+

B

y

A_x + B_y

The value of Ax? + By?

Similar to bfs:

First put in the priority queue
{

1

,

1

,

A

1

+

B

1

}

\{1,1,A_1 + B_1\}

{1,1,A1? + B1?} .
output each time
v

a

l

val

val has the smallest value, delete it, and then put it in

{

x

,

y

,

A

x

+

1

+

B

y

}

\{x,y,A_{x + 1} + B_y\}

{x,y,Ax + 1? + By?} and

{

x

,

y

,

A

x

+

B

y

+

1

}

\{x,y,A_x + B_{y + 1}\}

{x,y,Ax? + By + 1?} (use map to record whether it is repeated).
n

n

Loop n times.