Heap and priority queue in C++

Heap and priority queue are commonly used data structures in C, and they both have important application value. This article will introduce and analyze the heap and priority queue respectively to help readers better understand and use them.

1. Heap

The heap is a special tree data structure that can be used to implement priority queues. In the heap, each node satisfies the following properties:

1. Its value is not less than (or not greater than) the value of its parent node.
2. Its left and right subtrees are also a heap.

We call a heap that is no smaller than its parent node a "min heap" and a heap that is no larger than its parent node a "max heap". In addition, the heap is usually a complete binary tree, that is, the nodes in other levels are full except for the last level, where the nodes are arranged from left to right.

In C, the STL library provides two classes, heap and priority_queue, to implement the heap. Among them, the heap class provides heap operation functions, such as make_heap, push_heap, pop_heap, etc., and the priority_queue class is a priority queue based on the heap implementation. Next, let's take a look at the usage of heap and priority_queue.

1. heap class

(1) Create a heap

Before creating a heap, you need to create a vector type array to store the numbers to be sorted ：

vector v = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 };

Then, we can use the make_heap function to vector The array of type is converted to a heap:

make_heap(v.begin(), v.end(), greater());

where greater() means Comparison function can control the type of heap.

(2) Insert elements

To insert elements into the heap, you can use the push_heap function. Its usage is as follows:

v.push_back(7);
push_heap( v.begin(), v.end(), greater());

(3) Delete elements

To delete elements in the heap, you can use the pop_heap function, which will The top element of the heap is moved to the last position of the heap and the element is removed from the heap. The usage of this function is as follows:

pop_heap(v.begin(), v.end(), greater());
v.pop_back();

2. priority_queue class

(1) Create a heap

Unlike the heap class, the priority_queue class can specify the type of heap when declaring the object, as follows:

priority_queue, greater> q;

This means creating a minimum heap.

(2) Insert elements

Inserting elements into priority_queue can directly use the push function, as shown below:

q.push(2);
q. push(4);
q.push(1);
q.push(9);

(3) Delete elements

You can use it directly to delete elements in priority_queue The pop function is as follows:

q.pop();

2. Priority queue

The priority queue is a special queue that sorts elements according to their priority. Sort and place the elements with the highest priority at the front of the queue and the elements with the lowest priority at the end of the queue. You can use a heap to implement a priority queue.

In C, the priority_queue class is a priority queue implemented based on the heap. It can use the functions in the above heap and priority_queue classes to perform element insertion and deletion operations. In addition, the top function is also provided in the priority_queue class, which is used to access the element with the highest priority, as shown below:

priority_queue q;
q.push(2);
q .push(4);
q.push(1);
q.push(9);
cout

Summary:

This article introduces the heap and priority queue in C, and analyzes the usage and implementation principles of the heap and priority queue respectively. By studying this article, readers can better understand these two data structures and use them flexibly in actual programming. At the same time, readers should pay attention to the timing and precautions for using the heap and priority queue to ensure the correctness and efficiency of the code.

The above is the detailed content of Heap and priority queue in C++. For more information, please follow other related articles on the PHP Chinese website!