Shulou(Shulou.com)06/02 Report--

The main content of this article is to explain "how to open the heap in the Java collection". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let the editor take you to learn "what is the way to open the heap in the Java collection"?

What is a heap?

Heap is actually a special kind of queue-priority queue.

The general rules of the queue game are simple: first-in, first-out; but this kind of priority queue is special, not according to the time order of entering the queue, but according to the priority of each element, with the highest priority at the top of the stack.

This is also easy to understand, for example, all kinds of software have a membership system, a certain software can be downloaded quickly with members, different levels of members are not the same, that is, the priority is different.

And in fact, everyone replied to the Wechat message is to silently put the message into the pile in order: first back to boyfriend and girlfriend, and then back to others.

Here to be different from the operating system in the "heap", although these two are called heaps, but do not have a dime relationship, are borrowed from the English word Heap.

Let's review the position of the "heap" in the entire Java collection framework:

That is to say,

PriorityQueue is a class (class)

PriorityQueue inherits from the interface Queue (Interface)

So where is heap?

Heap is actually an abstract data structure, or a logical data structure, not a physically real data structure.

There are actually many ways to implement heap, such as binomial heap, Fibonacci heap, and so on. But the most common and classic interview is the binary heap binary heap, which is realized with a complete binary tree.

How is the complete binary tree realized?

In fact, it is realized with an array!

So binary heap/PriorityQueue is actually implemented as an array.

The arrangement of this array is a bit special because it always maintains that the element with the highest priority you define (or default) is at the top of the array, so not any array is called "heap". It should be a "complete binary tree" in your mind.

This complete binary tree exists only in your heart and on all the major books; actually, it is in memory, where is there a tree? It's just an array.

So why can a complete binary tree be implemented as an array? Can all trees be implemented in arrays?

This involves the nature of a complete binary tree, and we will talk about it in detail in the next article. To put it simply, because the definition of a complete binary tree requires that it has no bubbles during sequence traversal, that is, it can be stored in an array; the second question, of course, is whether or not.

Characteristics of the reactor

1. Heap is a complete binary tree.

two。 Heap order: any node is better than all its children.

a. If any node is larger than all its children, such a heap is called Max Heap.

b. If any node is smaller than all its children, such a heap is called small top heap, Min Heap

The picture on the left is a small top heap, which can be seen that for each node, it is smaller than all its children. Pay attention to all the children, including grandchildren and great-grandchildren.

3. Since the heap is implemented as an array, we can find the relationship between each node and its parents / children, so that we can access them directly.

For example, for node 3

Its Index = 1

Its parent index = 0

Left child left child index = 3

The right child right child index = 4.

The following rules can be summed up:

Let index = x of the current node

So parent index = (xMui 1) / 2

Left child left child index = 2cm x + 1

The right child right child index = 2cm x + 2.

Some books may be written in a slightly different way because their arrays start with 1, while here the subscript of the array starts with 0, which is OK.

In this way, we can find its grandchildren and great-grandchildren from any point in one step, which is really very convenient. When we talk about the specific operation later, we can understand it more deeply.

Basic operation

Any data structure is nothing more than adding, deleting, modifying and checking four categories:

Time complexity of functional method increases offer (E) O (logn) deletion poll () O (logn) to no direct API deletion + add search peek () O (1)

Here the time complexity of peek () is easy to understand, because the purpose of the heap is to quickly get the maximum / minimum values in a set of data, so the time complexity of this step must be O (1), which is what the heap is all about.

So let's look at the process of offer (E e) and poll ().

Offer (E e)

For example, we add a new 0 to the smallest heap just now:

It's obvious that 0 is to be put on top, but it's not a complete binary tree if you just put it on it.

So,

Let's make sure that after adding elements, the tree is still a complete binary tree.

Then fine-tune it in the way of swap to satisfy the stacking order.

This ensures that the two characteristics of the heap are met, that is, it is still a heap after the addition of new elements.

What exactly do you do?

Step 1.

Put 0 on the last connection first, don't think about it as soon as you come up.

OK! We finally got ashore first, and then we went up step by step.

The criterion of "going up" here is:

Whether it satisfies the stacking property.

That is, now that the stacking property is not satisfied between 5 and 0, then swap places until the stacking property is satisfied.

The stacking property here for the smallest heap is that the small number should be on top.

Step 2. Exchange with 5

At this point, 0 and 3 do not satisfy the stacking property, so swap again.

Step 3. Exchange with 3

Not yet, 0 is less than 1, so keep changing.

Step 4. Exchange with 1

OK! In this way, a new heap was born.

Summarize this method:

Add the new element to the end of the array, and then decide whether to swap it or not by constantly comparing the value with parent until the stacking is satisfied.

This process is called siftUp (), and the source code is as follows:

Time complexity

It is not difficult to find here, in fact, we have only exchanged elements on a branch road.

That is, the maximum number of exchanges is O (height).

So for a complete binary tree, except for the last layer, O (height) = O (logn).

So the time complexity of offer (E e) is O (logn).

Poll ()

Poll () is to take away the top element.

By the way, there is no way to take away the elements in the middle. After all, VIP has to go out first before my brother can go out.

Then when the topmost element is taken away, the position is empty:

Let's first satisfy the stacking order, because it's easier to be satisfied. Just take one from the back to make up, and put a puppet up first.

Step1. Upper position of the last element

In this way, the stacking property is not satisfied again, and the elements are exchanged.

Then 8 is bigger than 7 and 3. Who should I trade with?

Suppose you exchange with 7, then 7 is still bigger than 3, and you have to change 7 and 3.

So it's an exchange with the younger of the left and right children.

Step 2. Exchange with 3

After going down, it's bigger than 5 and 4, so trade with 4 again.

Step 3. Exchange with 4

OK! So the tree is finally stable.

Summarize this method:

First add the last element of the array to the top, and then decide whether to swap it or not by constantly comparing the value with the left and right child until the stacking order is satisfied.

This process is called siftDown (), and the source code is as follows:

Time complexity

By the same token, only one element on the branch is exchanged, that is, O (height) times at most.

So the time complexity of offer (E e) is O (logn).

Heapify ()

There is also a famous very important operation, which is heapify (), which is a very magical operation.

You can use O (n) time to turn a disordered array into a heap.

However, heapify () is not a public API. Look:

So we can't use it directly.

The only way to use heapify () is to use PriorityQueue (Collection c)

When this constructor, people will automatically call heapify () this operation.

So how exactly is it done?

Haha the source code has been exposed:

Start with the last non-leaf node and do siftDown () from back to front.

Because the leaf node does not need to operate, it has reached the bottom, who else can swap with?

For example:

We want to heapify () this array, we want to turn it into a minimum heap and get its minimum value.

Then we should start with 3 and siftDown () on 3, 7, 7 and 5.

Step 1.

Awkward? 3 does not need to be exchanged, because the little tree with it as its apex has satisfied the stacking order.

Step 2.

7 is older than both of his children, so trade with the younger one.

After the exchange is completed

Step 3.

The last thing to deal with is 5, which is older than its two children, so trade with the younger one.

After the change, the results are as follows, note that the stacking property is not satisfied, because 4 is smaller than 5.

So then switch with 4, and the result is as follows:

This completes the whole process of heapify ().

Okay, here comes the difficulty. Why is the time complexity O (n)?

How to calculate this time complexity?

In fact, all we do in this process is exchange.

How many times has it been exchanged?

Yes, the time complexity is as many times as it is swapped.

Then we can see that, in fact, the maximum number of exchanges between nodes on the same layer is the same.

Then the total number of exchanges = the number of nodes per layer * the maximum number of exchanges per node

Here, let k be the number of layers, so in this example, k is 3.

At this point, I believe you have a deeper understanding of "what is the way to open the heap in the Java collection?" you might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.