The article is included in the first original dry goods public number: Bigsai before you can see this article handwritten heap sort

preface

It all starts with a story:

First, I’m going to tell the cute dog that the data structure you need to use for this kind of problem is a priority queue, and the time for each operation is O(logn), and the time for the whole process is O(nlogn).

The design and implementation of this video may be somewhat similar to heapsort because they both use heaps to implement algorithms and data structures. The design and implementation of priority queues are described in detail below.

The heap

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

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

For complete binary treesI think you can understand that the lowest leaf node is strictly left to right. There are large piles and small pilesIf all the parent nodes are larger than their children, then this is a large root heap. If all the parent nodes are larger than their children, then this is a small root heap.The last thing to notice is that instead of storing the binary tree as a chain, we’re storing it as aArray to store the treeAlthough there may be more use scenarios of chain type, the space utilization rate is better in the case of complete binary tree without inclined tree. And in the operation can be directly through the number to find the location for exchange.

Priority queue

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

Priority queue, it’s a queue. A normal queue follows a first-in, first-out rule. The priority queue follows a sort rule: each throw custom sort is the largest (small), the default is to throw the smallest, this paper will be analyzed from the most basic principle.

And it uses the queue the same way, so we’re going to design this class to be consistent with the QUEUE API.

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

There are some operational differences between priority queue and heap sort, although there are some similarities in the process of taking advantage of heap structure characteristics:

Heap sort:

  • It starts out as a cluttered sequence, so you need a method to turn the cluttered sequence (tree) into a legitimate heap.
  • You have to delete it n times after you convert it to a heap and then you have to readjust the heap every 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. The heap should also be adjusted for each deletion, adding and removing only one element at a time.

But how does a priority queue work? We analyze the insert and delete process in detail.

Insert the Add process (small root heap for example) :

  • Normally processed priority queue data meets the structure of a heap, so it is inserted into the heap.
  • The heap is a complete binary tree, so at the beginning of the insertion, the insertion to the last position does not affect other structures.
  • The size of the node is compared to that of the parent node (the parent node has an index of 1/2). If the node is smaller than the parent node, the data is exchanged until it cannot be exchanged. This process is not illegal, because the parent node is smaller than the child node is more satisfied.

Remove the POP process (small root heap for example) :

  • The pop delete takes the smallest element in the priority queue, which must be the top of the heap. After that, the rest of the heap still satisfies the heap structure but lacks the top of the heap.
  • 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 heap properties.
  • This node is compared with the left and right children. If it needs to be swapped, it will be swapped. After the swap, it will consider whether the child nodes need to be swapped again until it does not. The worst case is to switch to the root node, which is O(logn) each time.

Code implementation

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

On the implementation side of the code, the most important are the pop() and add() functions. When the pop() function is implemented, move the last element to the stack and consider swapping with other child nodes, and make sure that the child subscript is computed with the while operation. We’re using arrays to store data, and the length of the priority queue doesn’t necessarily equal the length of the array.

When implementing the add() function, we simply consider capacity expansion.

The specific implementation code is:

import java.util.Arrays;

public class priQueue {

    private  int size;// Priority queue size
    private  int capacity;// The capacity of the array
    private  int value[];// The stored value

    public priQueue(a) {
        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;
    }

    /** * insert element *@param number
     */
    public void add(int number) {
        if(size==capacity)/ / capacity
        {
            capacity*=1.5;
            value= Arrays.copyOf(value,capacity);
        }
        value[size++]=number;// Add to the end first
        int index=size-1;
        while (index>=1) {// Do the swap
            if(value[index]<value[index/2]) {
                swap(index,index/2,value);
                index=index/2;
            }
            else// Stop without exchanging
                break; }}public int peek(a) {
        return  value[0];
    }

    /** * Throws the team head *@return* /
    public int pop(a) {
        int val=value[0];// Return the amount of data
        value[0]=value[--size];// Assign the last element to the stack header
        int index=0,leftChild=0,rightChild=0;
        while (true)
        {
            leftChild=index*2+1;
            rightChild=index*2+2;
            if(leftChild>=size)// The left child must meet the conditions
                break;
            else if(rightChild<size&&value[rightChild]<value[index]&&value[rightChild]<value[leftChild])
            {// The right child is smaller
                swap(index,rightChild,value);
                index=rightChild;
            }
            else if(value[leftChild]<value[index])
            {// The left child is smaller
                swap(index,leftChild,value);
                index=leftChild;
            }
            else // It doesn't need to be minimal by itself
                break;
        }
        return  val;
    }
    // Swap two elements
    public  void swap(int i,int j,int arr[]) {
        int team=arr[i];
        arr[i]=arr[j];
        arr[j]=team;
    }

    public int size(a) {
        returnsize; }}Copy the code

Write a class to test it:

conclusion

This introduction to priority queue here, feel good remember to like attention oh, suggest and heap sort together to see and learn the effect is better, to be able to handwritten code. Bigsai reply bigsai more wonderful and resources to share with you.