The article is included in the first official account:
bigsaiLooking forward to your visit!

preface

It starts with a story:





For the cute dog above, this is the tutorial. First of all, I will tell the cute dog that the data structure you need to use for this problem is the priority queue, and the time complexity of each operation is O(logn), and the time complexity of the whole process is O(nlogn).

The design and implementation of this film may be somewhat similar to heap sort, because they both implement algorithms and data structures with the help of heap. The design and implementation of priority queue are described in detail below.

The heap

Heap is a general term for a special class of data structures. A heap is usually an array of objects that can be viewed as a tree (complete). And always meet the following rules:

  • The heap is always a complete binary tree
  • Each node is always larger (or smaller) than its child nodes.

For a complete binary treeI think we all understand that the lowest leaf node is strictly from left to right.



Heaps have large and small root heapsIf all the parent nodes are larger than the children, then this is a large root heap; otherwise, this is a small root heap. Here is a large root heap:



The last thing to notice is that we’re not storing this binary tree in a chain but we’re storing it in a chainArray to store the tree, although the chained use scenario may be more, but in the case of complete binary tree space utilization is better and there is no oblique tree. And in the operation can be directly through the number of the location of the exchange.

Priority queue

To understand priority queues, let’s start with a conversation:

Priority queue, it’s a queue. A normal queue is on a first-in, first-out basis. However, the priority queue follows a sort rule: if the custom sort is the largest (smallest), the default situation is to throw the smallest. This article will analyze it from the most basic principle.

And its usage queue is still the same, so we have to design this class with the same API as the queue API.

We will mainly implement the add, poll, and peek methods and will focus on the implementation of the algorithm rather than the implementation of the details.

Although there are some similarities between the processes of priority queue and heap sort that take advantage of heap structure, there are actually some operational differences between the two:

Heap sort:

  • It starts out as a messy sequence, so you need a way to turn the messy sequence (the tree) into a legitimate heap.
  • Once you get to a heap you have to delete it n times and then you have to resize the heap each time you delete it. There is no insert operation.

Priority queue:

  • The queue (heap) starts out empty and needs to adjust the heap each time an element is added. Each delete also adjusts the heap, adding and removing only one element at a time.

But how does a priority queue work? We analyze the process of its insertion and deletion in detail.

Insert the Add process (small root heap example) :

  • The data in the priority queue after normal processing satisfies the structure of a heap, so it is inserted in the heap.
  • The heap is a complete binary tree, so at the beginning of the insert, the insertion into the last position does not affect the other structures.
  • Compare the size of the node to that of the parent node (the parent node index is one half). If the node is smaller than the parent, then the data is swapped until it cannot be swapped. This process does not have to be illegal because it is more satisfying for the parent to be smaller than the child.

Delete POP process (small root heap example) :

  • The pop delete takes the smallest element in the priority queue, which must be the top of the heap. After the pop delete, the rest of the heap still meets the structure of the heap but lacks the top.
  • In order not to affect the entire structure, we move the last element to the top of the heap, where the heap needs to be adjusted to meet the heap property conditions.
  • The node to be swapped is compared with the left and right children. If it needs to be swapped, then it is swapped. After swapping, it is considered again whether the swapped child nodes need to be swapped until no swapping. The worst case is to swap to the root node, which is order logn at a time.

Code implementation

I think here, you have mastered the idea of the internal process of priority queue, but understand the principle of priority queue and handwritten priority queue are two concepts, in order to learn more in-depth priority queue, here I will take you handwritten a simple priority queue.

In the specific implementation of the code, the most important is the pop() and add() two functions. When implementing pop(), move the last element to the head of the heap to consider swapping with other children, and when calculating the child subscript with a while, make sure that the bounds are not crossed. We’re using an array to store data, and the length of the priority queue is not necessarily the same as the length of the array.

In the implementation of the add() function, there is a simple consideration of capacity expansion.

The code for specific implementation is as follows:

import java.util.Arrays; public class priQueue { private int size; Private int capacity; private int capacity; Private int value[]; Public PriQueue () {this.capacity = 10; this.value = new int[capacity]; this.size=0; } public priQueue(int capacity) { this.capacity = capacity; this.value = new int[capacity]; this.size=0; Public void add(int number) {if(size==capacity)// Capacity *=1.5; value= Arrays.copyOf(value,capacity); } value[size++]=number; Int index=size-1; While (index>=1) {if(value[index]<value[index/2]) {swap(index,index/2,value); index=index/2; } else// stop break without exchanging; } } public int peek() { return value[0]; Public int pop() {int val=value[0];} public int pop() {int val=value[0]; // value[0]=value[--size]; Int index=0,leftChild=0,rightChild=0; while (true) { leftChild=index*2+1; rightChild=index*2+2; If (leftChild>=size)// The leftChild must break in the condition; Else if(RightChild <size&&value[RightChild]<value[Index]&&value[RightChild]<value[leftChild]) swap(index,rightChild,value); index=rightChild; } else if(value[leftChild]<value[index]) {// Swap (index,leftChild,value); index=leftChild; } else // does not need its own minimum break; } return val; } public void swap(int I,int j,int arr[]) {int team=arr[I]; arr[i]=arr[j]; arr[j]=team; } public int size() { return size; }}

Write a class test to see:

conclusion

So that’s it for this introduction to priority queues,Feel good remember thumb up or one button three connect oh, it is suggested to see and learn better with heap sort, to be able to write the code. Personal official account:bigsaireplybigsaiMore highlights and resources to share with you.