Date:2021/02/17

Little me, still want to collide with the world

What is a pile of

A Heap, also known as a binary Heap, is a complete binary tree with the following properties:

  • Any parent node whose value is greater than or equal to the value of the child node is called a large top heap.
  • Any parent node whose value is less than or equal to the value of the child node is called a small top heap.

This property of the heap determines that the value of the top element (the root node) in the largest heap is the largest in the whole heap, and the value of the top element in the smallest heap is the smallest in the whole heap. With this property, heaps are often used for heap sorting, priority queues, and so on.

The heap said

Although the heap is a complete binary tree, we often use an array to represent the heap, depending on the properties of a complete quadratic tree: N (n≥0)n(n\ge0)n(n≥0) the complete binary tree of each node is numbered from top to bottom and from left to right starting from 000. For the I (0≤ I

  • I == 0I == 0I ==0, is the root node
  • I > 0 I > 0 I > 0, the serial number of the parent node as floor ((I – 1) / 2) floor ((I – 1) / 2) floor ((I – 1) / 2)
  • If 2i+1< n2I +1< n2I +1
  • If 2i+2< n2I +2< n2I +2

So a full binary tree can be mapped to an array whose length is the number of nodes, and the number above is the index of the array, as shown in the figure below.

The sequence of numbers and the storage of arrays are the result of hierarchical traversal.

Java can use ArrayList array directly:

public class BinaryHeap<E extends Comparable<E>>{
	private ArrayList<E> elements;
    	// ...
}
Copy the code

Self-tuning of the heap

Operations such as adding or removing a heap can break the nature of the heap. To maintain the characteristics of the heap, there are two operations, namely, floating and sinking.

Take the big top pile as an example.

floating

The essence of the float operation is to find a suitable node to replace the node that does not satisfy the characteristics of the heap. For example, the last node 20 of the big top heap in the figure below is larger than the parent node, which does not satisfy the property of the big top heap, so the node should be floated up.

First, 20 is compared with its parent node 9, and it is found that 20 is larger than 9, so 20 and 9 are swapped.

Continue to compare 20 to the parent node 10, and find that 20 is larger than 10, so swap 20 with 10,

In comparison with the parent node 21, 20 is smaller than 21, which satisfies the large top heap characteristic of the heap, so the float operation of node 20 is completed, and a large top heap is obtained.

In fact, in the process of floating, it is not necessary to exchange every time. You can first save the value of floating node, and then directly overwrite the child node with the value of the parent node when the exchange is needed. After the floating is over, you can use the previously saved floating node value to overwrite the last position of the exchange.

The implementation of the float operation is as follows:

/** * Float the heap node **@paramIndex Index of the floating node */
protected void upAdjust(int index) {
    if (index < 0 || index >= elements.size()) {
        throw new IndexOutOfBoundsException("Heap node index out of bounds!");
    }
    int parent = parent(index);
    E temp = this.elements.get(index);
    while (parent >= 0 && this.elements.get(parent).compareTo(temp) < 0) {
        this.elements.set(index, this.elements.get(parent));
        index = parent;
        parent = parent(index);
    }
    this.elements.set(index, temp);
}
Copy the code

sinking

The sink operation is similar to the float operation in that the sink is looking down for a suitable node to replace. Sinking, unlike floating, requires comparing and replacing the parent node with the larger value of the left and right children (the small top heap is the smaller value).

For example, the root node 9 in the figure below does not satisfy the property of large top heap and needs to be sunk.

The left child is bigger than the left child of node 9. Compare 9 to the left child of node 20. The left child is bigger.

The left child 10 is bigger than the left child 10. Compare 9 with the left child 10. The left child is bigger.

Node 9 has only the left child, but the left child is smaller than node 9, which satisfies the property of large top heap, so the sinking operation of node 9 is completed.

Just like floating up, there’s actually no real exchange.

The sinking operation is implemented as follows:

/** * Stack node sink operation **@paramIndex Index of the sinking node */
protected void downAdjust(int index) {
    if (index < 0 || index >= elements.size()) {
        throw new IndexOutOfBoundsException("Heap node index out of bounds!");
    }
    E temp = this.elements.get(index);
    int childIndex = leftChildren(index);
    while (childIndex < this.elements.size()) { 
    	// Entering the loop indicates that there is a left child
        if (childIndex + 1 < this.elements.size() && this.elements.get(childIndex).compareTo(this.elements.get(childIndex + 1))"0) {
            // Enter if to indicate the right child and the right child is older than the left child
            // Set childIndex to the right child
            childIndex++;
        }
        if (temp.compareTo(this.elements.get(childIndex)) > 0) {
            break;
        }
        this.elements.set(index, this.elements.get(childIndex));
        index = childIndex;
        childIndex = leftChildren(index);
    }
    this.elements.set(index, temp);
}
Copy the code

The operation of the heap

Add elements

To ensure that the heap is always a full binary tree, you can only add elements to the end, which is the last position in the array. Adding elements is a two-step process:

  • Add the new element to the end (make sure it’s a full binary tree)

  • Float new elements (ensure heap size relationship)

Remove elements

To delete an element is to remove the top element of the heap, that is, to delete the maximum or minimum value. To delete an element:

  • Replace the top element of the heap with the last element
  • Delete the last element (the last element is a leaf node)
  • Sinks the top element of the heap

In the maximum heap below, to remove the top element 21, replace the top element with the last node 9, remove node 9, and then drop the top node.

The sinking process was mentioned earlier.

Create a heap

To create a heap is to sink all the non-leaf nodes of a normal full binary tree in order of the largest to smallest array indices.

The last non-leaf node has the following properties:

  • For a complete binary tree with NNN nodes, the index of the last non-leaf node is (n−2)/2(N-2)/2(n−2)/2.

To convert a complete binary tree below into a large top heap, the non-leaf nodes (red nodes) need to be sunk from back to front.

First of all, nodes 21 and 14 have satisfied the large top heap, and no operation is required.

Then sink node 2,

Then the node 10 is sunk, and the binary heap construction is completed.

Complexity analysis

The insertion of the heap is actually the floating operation of a single node, and the deletion of the heap is actually the sinking operation of a single node, so the time complexity of the insertion and deletion of the heap is O(logn).

While building a heap is to sink all non-leaf nodes, but the time complexity is not simple O(nlogn), but **O(n)**. This is because the maximum number of non-leaf nodes to sink at each layer is different. For a complete binary tree with NNN nodes, The height can be thought of as h=lognh=lognh=logn:

  • There are 111 nodes at layer 000, and a maximum of layers H −0− 1H-0-1H −0−1 need to be sunk

  • Layer III contains 2I2 ^ i2I nodes. A maximum of layers H − I − 1H-i-1H − I −1 need to be sunk

  • So add the time of each node: S = 20 ∗ ∗ (h – 1) + 21 (h – 2) + ⋅ ⋅ ⋅ ∗ + 2 h – 1 (0) = 2 ^ 0 S * (h – 1) + 2 ^ 1 * (h – 2) + \ cdot \ cdot \ cdot + 2 ^ {} h – 1 * (0) S = 20 ∗ ∗ (h – 1) + 21 (h – 2) + ⋅ ⋅ ⋅ ∗ + 2 h – 1 (0)

The time complexity of the sequence is O(n).