【 Recommended reading 】

  • Use diagrams and code to make you understand the sequential structure of linear tables
  • After reading this article, I finally understand the linked list
  • 【 Data structure of the stack 】 With detailed pictures and texts to understand the “stack” (Principle)
  • The queue of data structures Learning queues, read this one is enough!
  • 【 Data structure linked list 】 detailed graphics teach you tricks to play linked list
  • [Data structure of binary tree] to understand the concept and principle of binary tree
  • Data structure of binary tree binary tree creation and traversal implementation
  • Cue binary trees for data Structures: The principle and creation of cue binary trees
  • Binary heap principle and operation of binary heap

First remember the queue (move to queue for details), just remember eight words: first in, first out (FIFO), last in, last out (LILO).

It’s like waiting in line at the outpatient clinic: first come, first go.

The feature of the priority queue is the word “priority”, which means breaking the “convention” and “rule”.

Priority queues no longer follow the first-in, first-out principle of normal queues. How?

  • Maximum priority queue: Regardless of the queue order, who has the highest value and who leaves the queue first
  • Minimum priority queue: Regardless of the queue order, who has the smallest value and who leaves the queue first

For example, for the maximum priority queue, the queue entry order is 14352, and the queue exit order is 54321; For the minimum priority queue, the queue entry order is 14352, and the queue exit order is 12345.

For example, hospital emergency cases, even if they come late, can be treated first, because life is Paramount. In the event of disaster, children are the first to be evacuated.

It’s not good to talk about fifO rules when you need to talk about priority.

So how do you implement priority queues?

First of all, in a priority queue, to get out of the queue, you must first find the maximum or minimum value;

Second, priority queues are “non-conventional”, so it doesn’t matter what order you queue in. What matters is finding the maximum or minimum value in the current queue.

So, is there a way to find a maximum or minimum directly, regardless of the other order?

There are! This method is binary heap! (For details, please move to binary heap.)

  1. The heap top of a binary heap is the maximum or minimum value in the heap
  2. You insert a node, you insert it at the end of the binary heap, and then you adjust it again to form the binary heap
  3. Deleting a node removes the top of the heap, which is then adjusted again to form a binary heap

So you can use binary heap to achieve priority queue, maximum heap to achieve maximum priority queue, minimum heap to achieve minimum priority queue

  1. Out of line means out of line
  2. To join a queue, you insert a node into the binary heap
  3. The heap top is deleted when out of the queue

A match made in heaven! Perfect ~

Below is the code implementation of the maximum priority queue.

The structure of the priority queue is the structure of the binary heap:

typedef struct {
    int array[MAXSIZE];
    int length;
} BinaryHeap, PriorityQueue;
Copy the code

Team entry operation:

/** * @description: Queue entry * @param {PriorityQueue} *queue queue pointer * @param {int} elem entry element * @return {*} None */
void en_max_queue(PriorityQueue *queue.int elem)
{
    insert_into_max_heap(queue, elem);
}
Copy the code

Queue operation:

/** * @description: maximum PriorityQueue outgoing * @param {PriorityQueue} *queue queue pointer * @param {int} *elem save variable pointer * @return {*} none */
void de_max_queue(PriorityQueue *queue.int *elem)
{
    delete_from_max_heap(queue, elem);
}
Copy the code

Insert_into_max_heap and delete_from_max_heap have been implemented in the article, and will not be described here.

So that’s the priority queue.

Complete code please visit lot | Gitee acquisition.

Please correct me if there are any mistakes.

If you think it’s good, you can like it and follow it. More data structures and algorithms will follow.