The basics of binary heap~

Binary heap: a complete binary tree

Complete binary tree: A full binary tree is missing a lower right corner

Two characteristics of the heap:

1. A binary heap is first a complete binary tree (structurally)

2. The relationship between binary heap nodes satisfies the following relationship:

The value of the root node in the heap>=the value of the node in the subtree (max heap/big root heap)

The value of the root node in the heap<=the value of the node in the subtree (min heap/small root heap)

In the large root heap, only the current root node can be guaranteed to be greater than or equal to all nodes of the subtree, and in any subtree Still satisfied

But the size of the node has nothing to do with the level.

Complete binary tree (including full binary tree) is recommended to use sequential table storage (array)

In a complete binary tree, there is no such thing as only the right subtree and no left subtree, so there is no need to store empty nodes

Other binary trees are not recommended.

Ordinary binary trees are not suitable for array storage, because it will waste a lot of space to store the control number.

---

How to judge whether a node K has a subtree using only the index?

2k+1 (because a full binary tree can have no right subtree)

Given a node k, how to determine whether its parent node exists?

Just look at the number of the parent node > 0

The index of the parent node is (k - 1) >> 1

---

Add an element to a large root heap and find the corresponding position:

public void add(int val){data.add(val);// Carry out the floating operation of the elementshiftUp(data.size() -1);}private void shiftUp(int k) {// element float operation// Termination condition: reach the root node or the current node value <= parent node valuewhile(k >0 && data.get(k) > data.get(parent(k))){// Termination condition not met//Swap the value of the current node and the parent nodeswap(k,parent(k));k = parent(k);}}private void swap(int i, int j) {int temp = data.get(i);data.set(i,data.get(j));data.set(j,data.get(i));}

Continue to extractMax from the max heap until the heap is empty, we can get an array in descending order.

 //Get the maximum value of the current maximum teampublic int extractMax(){// Pay attention to the value of emptyif(isEmpty()){throw new NoSuchElementException("heap is empty cannot extract!");}//The large root heap defaults to the largest element with the root nodeint max = data.get(0);//1. Push the end element of the array to the top of the heapint lastVal = data.get(data.size()- 1);data.set(0,lastVal);//2. Delete the element at the end of the arraydata.remove(data.size() -1);//3. Perform the sinking operation of the elementshiftDown(0);return max;}private void shiftDown(int k) {// there are still subtreeswhile(leftChild(k) < data.size()){int j = leftChild(k);// Determine if there is a right treeif(j+1 < data.size() && data.get(j +1) >data.get(j)){//At this time, the right tree exists and is greater than the value of the left treej = j+1;}//At this time, j corresponds to the maximum value of the left and right subtrees//Compare with the current kif(data.get(k) >data.get(j)){// end of sinkingbreak;}else{swap(k,j);k = j;}}}

In theory, when testing data, only a small set can not be used. We use ThreadLocalRandom to generate a large set of 10w data, which can solve the competition between multiple threads.

Here is the reason for my error: ThreadLocalRandom cannot instantiate new, just use its static method current directly

Changing from Math.random() to ThreadLocalRandom has the following benefits:
We no longer have contention to access the same random number generator instance from multiple threads.
Instead of instantiating one random number generator instance per random variable, we can instantiate one per thread.

---

heapify -- heapify: resize any array into a heap structure

Idea 1 (time complexity NlogN):

1. Treat any array as a complete binary tree

2. Step by step call the add method to insert these N elements into a new heap to get a maximum heap

int[] data = {15,17,19,13,22,16,28,30,41,62};// step by step into the heapMaxHeap heap = new MaxHeap();for(int i :data){heap.add(i);//Add an element, which contains the element floating}System.out.println(heap);

In the shiftUp method, k = parent(k), divide by 2, which is the height of the binary tree.

Thinking 2 (time complexity N):

1. Let any array be regarded as a complete binary tree traversal

2. The sinking operation of the element from the last non-leaf node of the current complete binary tree can be adjusted to a heap

So how to find this non-leaf node?

The parent node of the last leaf node is!

The last leaf node---the last element of the array

int lastNodeLeafNode = pareant(data.size() -1);

public MaxHeap(int[] arr){data = new ArrayList<>(arr.length);// first copy all elements of arr to the data arrayfor(int i :arr){data.add(i);}//Start shiftDown from the last non-leaf nodefor (int i = parent(data.size() -1); i >= 0 ; i--) {shiftDown(i);}}