Mp.weixin.qq.com/s?__biz=MzI…

Little Grey programmer little grey 1 week ago

Click “programmer small Grey” above, choose to pay attention to the public account

Interesting and meaningful articles are delivered at the first time!

 

 

 

 

————— the next day —————

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

— — — — — —

 

 

 

 

 

 

 

 

What is a binary heap?

 

Binary heap is essentially a complete binary tree, which is divided into two types:

1. The maximum heap

2. The minimum heap

 

What’s the biggest pile? The maximum value of any parent node is greater than or equal to the values of its left and right children.

 

 

 

What is minimum heap? The value of any parent node of the minimum heap is less than or equal to the values of its left and right children.

 

 

 

The root node of the binary heap is called the top of the heap.

 

The characteristics of the maximum heap and the minimum heap determine that the top of the maximum heap is the largest element in the whole heap; The top of the smallest heap is the smallest element in the entire heap.

 

 

 

 

 

Heap self-tuning

 

For binary heaps, there are several operations:

Insert the node

Remove nodes

Build a binary heap

 

All of these operations are based on heap self-tuning.

 

Let’s take a look at how binary heaps adjust themselves using the smallest heap as an example.

 

1. Insert the node

 

The node of the binary heap is inserted at the last position in the complete binary tree. Let’s say we insert a new node with a value of 0.

 

 

 

In this case, we compare node 0 to its parent node 5. If 0 is less than 5, we let the new node float up and swap places with the parent node.

 

 

 

Continue to compare node 0 to parent node 3, and if 0 is less than 3, let the new node continue to float up.

 

 

 

The comparison continues, eventually allowing the new node 0 to float up to the top of the heap.

 

 

 

 

2. Delete the node

 

The process of node deletion in binary heap is the opposite of the process of insertion. The nodes at the top of the heap are deleted. For example, we delete the top node 1 of the smallest heap.

 

 

 

At this point, to maintain the complete binary tree structure, we add the last node of the heap, 10, to the original position of the top of the heap.

 

 

 

Next we compare node 10, which moves to the top of the heap, to its left and right children, and let node 10 “sink” if the smallest of the left and right children (obviously node 2) is smaller than node 10.

 

 

 

Continue to compare node 10 to its left and right children, the youngest of which is node 7. Since 10 is greater than 7, let node 10 continue to “sink.”

 

 

 

In this way, the binary heap is re-tuned.

 

 

3. Build a binary heap

 

Building a binary heap, that is, adjusting an unordered complete binary tree to a binary heap, essentially allows all non-leaf nodes to sink in sequence.

 

Let’s take an example of an unordered complete binary tree:

 

 

 

First, we start with the last non-leaf node, node 10. If node 10 is larger than the smallest of its left and right children, node 10 sinks.

 

 

 

Next comes node 3, which sinks if it is larger than the smallest of its children.

 

 

 

 

Next comes node 1, which sinks if it is larger than the smallest of its children. Node 1 is actually smaller than its left and right children, so you don’t have to change it.

 

Next comes node 7, which sinks if it is larger than the smallest of its children.

 

 

 

Node 7 continues to compare and sink.

 

 

 

In this way, an unordered complete binary tree is constructed as a minimum heap.

 

 

 

 

 

 

Heap code implementation

 

Before we do this, we need to be clear:

 

Although binary heap is a complete binary tree, its storage mode is not chain storage, but sequential storage. In other words, all nodes of the binary heap are stored in an array.

 

 

How do you locate the left and right children of a parent node in an array without left and right Pointers?

 

As in the figure, we can rely on array subscripts to calculate.

 

If the subscript of the parent node is parent, then its left child subscript is 2*parent+1. Its right child subscript is 2*parent+2.

 

For example, in the example above, node 6 contains two children, 9 and 10. The subscript of node 6 is 3, node 9 is 7, and node 10 is 8.

 

7 = 3 * 2 + 1

8 = 3 * 2 + 2

 

It just fits the pattern.

 

 

With this premise in mind, the following code makes more sense:

 

public class HeapOperator {

 
Copy the code
  1. / * *
  2. * Float up adjustment
  3. * @param array Specifies the heap to be adjusted
  4. * /
  5. public static void upAdjust(int[] array) {
  6.    int childIndex = array.length-1;
  7.    int parentIndex = (childIndex-1)/2;
  8. // temp holds the value of the inserted leaf node for the final assignment
  9.    int temp = array[childIndex];
  10.    while (childIndex > 0 && temp < array[parentIndex])
  11.    {
  12. // No real exchange, one-way assignment
  13.        array[childIndex] = array[parentIndex];
  14.        childIndex = parentIndex;
  15.        parentIndex = (parentIndex-1) / 2;
  16.    }
  17.    array[childIndex] = temp;
  18. }
  19.  
  20.  
  21. / * *
  22. * Sinking adjustment
  23. * @param array Specifies the heap to be adjusted
  24. * @param parentIndex The parent node to sink
  25. * @param parentIndex The effective size of the heap
  26. * /
  27. public static void downAdjust(int[] array, int parentIndex, int length) {
  28. // temp holds the parent value for the final assignment
  29.    int temp = array[parentIndex];
  30.    int childIndex = 2 * parentIndex + 1;
  31.    while (childIndex < length) {
  32. // If there is a right child and the value of the right child is smaller than the value of the left child, locate the right child
  33.        if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
  34.            childIndex++;
  35.        }
  36. // If the parent node is smaller than any of the children, jump out
  37.        if (temp <= array[childIndex])
  38.            break;
  39. // No real exchange, one-way assignment
  40.        array[parentIndex] = array[childIndex];
  41.        parentIndex = childIndex;
  42.        childIndex = 2 * childIndex + 1;
  43.    }
  44.    array[parentIndex] = temp;
  45. }
  46.  
  47.  
  48. / * *
  49. * build a heap
  50. * @param array Specifies the heap to be adjusted
  51. * /
  52. public static void buildHeap(int[] array) {
  53. // Start from the last non-leaf node and drop down to adjust
  54.    for (int i = array.length / 2; i >= 0; i--) {
  55.        downAdjust(array, i, array.length - 1);
  56.    }
  57. }
  58.  
  59.  
  60.  
  61. public static void main(String[] args) {
  62. Int [] array = new int[] {1,3,2,6,5,7,8,9,10,0};
  63.    upAdjust(array);
  64.    System.out.println(Arrays.toString(array));
  65.  
  66. Array = new int[] {7,1,3,10,5,2,8,9,6};
  67.    buildHeap(array);
  68.    System.out.println(Arrays.toString(array));
  69. }

}

There is an optimization point in the code, that is, when the parent node and the child node do continuous exchange, do not really exchange, just need to exchange the value of one side into the temp variable, do one-way overwrite, after the end of the loop, and then the value of temp into the final position after the exchange.

 

 

 

 

 

 

 

 

 

A few points to add:

 

This cartoon is purely entertainment, but also please cherish the current work as much as possible, do not imitate the behavior of small gray oh.

 

 

 

 

— — the END — — –

 

 

 

If you like this article, please long click the picture below to follow the subscription number programmer Xiao Grey and watch more exciting content