1. What is binary heap?

“Binary” needless to say, the main trees introduced in this chapter are binary trees. So what is a heap?

In everyday life, we often say “a pile of things” or “a pile of things”, and by “pile”, we usually mean a lot of things placed on top of each other.

When we’re stacking things, we’ve all had a rule of thumb: to make the pile more stable, we put heavier, larger things on the bottom and lighter, smaller things on top.

The same lesson applies to data structures called binary trees. However, “heavy” and “large” are judged by the value of the node, and are compared between the parent node and the child node.

For example, the node with the highest value is the child node; A node with a small value is a parent node.

For example, let’s look at an ordinary binary tree, which is also a complete binary tree:

Look at the following binary heap:

The characteristics of this binary heap are:

• It’s a complete binary tree. In fact, the binary heap is transformed from the complete binary tree in the figure above;
• The value of any parent node is less than or equal to the value of the left child and the right child;
• Each branch is sorted ascending from the root (branch 1-2-3-4, for example).

Such A binary heap is called A minimum heap, and the top of the heap, the root node A, is the minimum of the entire tree.

Corresponding to the minimum heap is the maximum heap:

• The largest heap is a complete binary tree;
• The value of any parent node is greater than or equal to the value of the left child and the right child;
• Each branch is sorted descending from the root.

The top of the biggest heap is the maximum of the whole tree.

We convert the ordinary binary tree in the figure above into the maximum heap, as shown below:

2. Binary heap operation

2.1. Construct binary heap

Given a complete binary tree, how do you adjust the nodes to make a binary heap? Here is an unordered complete binary tree:

Now we want to construct a minimum heap by first finding all the non-leaf nodes in the complete binary tree (marked in green) :

What we’re going to do is “sink” the minimum heap for each non-leaf node.

What is the “sink” adjustment for the minimum heap?

For a non-leaf node, if the node is larger than the smallest of its children, the two positions are swapped, otherwise not. The graph shows non-leaf nodes (i.e., high-value nodes) “sinking” one level. The motion is relative, and the “sinking” of high-value nodes is equivalent to the “floating” of low-value nodes.

Note that sometimes sinking once is not enough, we need to sink multiple times to make sure the node sinks to the bottom (i.e. it is no longer larger than its child).

All non-leaf nodes, starting from the last, according to the order from right to left, bottom to top of the minimum heap sink adjustment, can be constructed into the minimum heap.

For example, if a non-leaf node with a value of 4 sinks to level 3 and is still larger than its child, it doesn’t “sink to the bottom” and needs to sink to level 4. At this point, “high value” node 4 sinks to the bottom on branch 2-4-3-1.

Here is a step-by-step explanation:

1. For non-leaf node 7, it is smaller than its child node 10 and does not “sink”;

   

2. For non-leaf node 3, which is larger than node 1, the larger of its children, node 3 “sinks” and swaps with node 1. Obviously, node three sinks to the bottom.

   

3. For non-leaf node 6, which is larger than node 5, the smaller of its children, node 6 “sinks”, swapping places with node 5. Obviously, node six sinks to the bottom.

   

4. For non-leaf node 4, which is larger than node 1, the smallest of its children, node 4 “sinks”, swapping places with node 1. Obviously, node 4 didn’t sink to the bottom.

   

5. Again, for node 4, which is larger than node 3, the smallest of its children, node 4 has to “sink” and swap places with node 3. At this point, node 4 is at the bottom.

   

6. For non-leaf node 2, which is larger than node 1, the smallest of its children, node 2 “sinks”, swapping places with node 1. Obviously, node two has sunk to the bottom.

   

At this point, we have adjusted an unordered complete binary tree into a minimum binary heap, and you can check that all nodes in the minimum heap are such that the values of the parents are less than the values of the children. And all five branches are ordered.

The steps for constructing the maximum heap are similar, but the sink adjustment for the maximum heap is that if a node is smaller than the largest of its children, the two positions are swapped, showing non-leaf (i.e., small-value) nodes “sink” one level on the graph. Through several sink adjustments, the node is no longer smaller than its child.

The following figure shows an unordered complete binary tree scaled to the maximum heap:

2.2. Insert nodes

A binary heap is a complete binary tree, and you insert nodes into it, just after the last node of the complete binary tree.

For example, if you insert node 11 into the largest heap at the bottom, you insert node 11 next to node 4. When node 11 is inserted into the maximum heap, it is no longer the maximum heap, because node 11 breaks the structure of the original heap. So, we should think of it as a new complete binary tree, and then adjust the new complete binary tree to construct the maximum heap again. (See above for adjustment process)

2.3. Delete nodes

The delete operation, as opposed to the insert operation, removes the element in the first position, that is, the top of the heap.

Let’s take removing the top 11 of the largest heap in the figure above as an example.

When top 11 of the heap is removed, the binary heap structure is broken, not even one binary tree (instead of two) :

In order to maintain the complete binary tree shape, we add the last node 7 to the root, replacing the deleted root 11. In this way, we have a new complete binary tree (not a binary heap), and then we can construct the maximum heap again from this new complete binary tree.

3. Storage structure of binary heap

The storage structure of binary heap is sequential storage, because binary heap is a complete binary tree, we said in “binary tree storage” : complete binary tree is suitable for using sequential storage structure to achieve.

Here is a maximum heap. The red box is the node number, corresponding to the array subscript.

The chain storage structure can clearly and vividly show us the relationship between the parent nodes and the left and right children in the binary heap. But there are no Pointers in the array, there are only subscripts in the array, how do we represent the relationship between parents and children?

In fact, for complete binary trees, array subscripts are sufficient!

Suppose that the array subscript of the parent node in the binary heap is parent_index, the array subscript of the left child is left_child_index, and the array subscript of the right child is right_child_index, then the relationship between them is as follows:

Left_child_index = 2 × parent_index + 1

(2) right_child_index = 2 × parent_index + 2

Parent_index = (left_child_index – 1) ÷ 2

Parent_index = (right_child_index – 2) ÷ 2

Right_child_index = left_child_index + 1

For example, if the subscript of node 3 is 3, the subscript of its left child 2 is 2 × 3 + 1 = 7, and the subscript of its right child 1 is 2 × 3 + 2 = 8.

The subscript of node 3 is 3. As the left child, its parent subscripts are (3-1) ÷ 2 = 1. The subscript of node 7 is 4. As a right child, its parent subscript is (4-2) ÷ 2 = 1.

So let’s say the array of some node is child_index, and you don’t know if this node is a left child or a right child, and you want the indices of its parents

(6) parent_index = (child_index – 1) ÷ 2

For example, if you don’t know whether node 5 (subscript 5) and node 6 (subscript 6) are left or right children, then the parent subscripts of node 5 and node 6 are (5-1) ÷ 2 = 2, (6-1) ÷ 2 = 2 respectively. (Note that integers are used in programming languages, so the result is not a decimal.)

Here, we use a structure to implement a binary heap:

#define MAXSIZE 20 // The maximum storage space of the array

typedef struct {
    int array[MAXSIZE]; // Store arrays
    int length; // The current heap size (node number)
} BinaryHeap;
Copy the code

Before we can do the actual operation, we need to initialize the binary heap, that is, assign the array and the heap length:

/** * @description: Initialize BinaryHeap * @param {BinaryHeap} *heap * @param {int} *array The array is an unordered complete binary tree * @param {int} arr_length Array length * @return {*} None */
void init_heap(BinaryHeap *heap, int *array.int arr_length)
{
    // Array is copied to the heap
    memcpy(heap->array.array, arr_length * sizeof(int));
    // Set the heap length
    heap->length = arr_length;
}
Copy the code

4. Concrete implementation of binary heap

4.1. Adjustment and construction

Here is an example of constructing a minimum heap.

To construct a minimum heap, you adjust all the non-leaf nodes. The adjustment is based on comparing the size of non-leaf nodes with their children.

We agree that parent is a non-leaf node and parent_index is its subscript. Child is the younger of its children, and child_index is its subscript.

Child starts by default identifying the left child, so the subscript for the right child is child_index + 1. When the left child is less than or equal to the right child, the child does not need to change; When the left child is larger than the right child, update child_index so that the child identifies the right child.

The following shows how the code is implemented using the example of a non-leaf node with a value of 4 in the figure below.

If the left child is smaller than the left child, the left child is the left child and does not need to update child_index.

Parent and Child are in position. If parent is larger than child, switch places. Parent_value = 4; parent_value = 4;

Swap: Assigns the value of child to parent to float 1:

Then update parent_index and child_index one level down:

Then assign the previously saved value to the current parent so that the value 4 sinks:

One adjustment is done, but it’s not over for value 4 because it hasn’t sunk to the bottom yet.

Child_index: child_index: child_index: child_index: child_index: child_index: child_index:

Now switch places and assign child to parent to float up to 3:

Then, update the values of parent_index and child_index one level down:

Assign value to parent to sink to value 4:

At this point, child_index has exceeded the length of the binary heap, i.e. the value 4 has reached the bottom.

The adjustment code is as follows:

/** * @description: * @param {BinaryHeap} *heap BinaryHeap (unordered) * @param {int} parent_index a non-leaf node * @return {*} none */
void adjust_for_min_heap(BinaryHeap *heap, int parent_index)
{
    // value holds the value of a non-leaf node
    int value = heap->array[parent_index];
    // child_index identifies the left child
    int child_index = parent_index * 2 + 1;
    // Index of the last node
    int last_child_index = heap->length - 1;

    Parent has at least one child
    while (child_index <= last_child_index) {
        // If parent has left and right children
        if (child_index < last_child_index) {
            // Compare the left child and the right child, if the right child is small,
            if (heap->array[child_index] > heap->array[child_index + 1]) {
                // then child_index identifies the right child
                child_index = child_index + 1; }}// If the parent value is greater than the child value
        if (value > heap->array[child_index]) {
            heap->array[parent_index] = heap->array[child_index]; // Small nodes float up
            parent_index = child_index; // Update the parent subscript
            child_index = parent_index * 2 + 1; // Update the child subscript
        } else { // No operation, out of the loop
            break;
        }
        // The big node sinks
        heap->array[parent_index] = value; }}Copy the code

The construction code is as follows:

/** * @description: construct minimum heap * @param {BinaryHeap} *heap BinaryHeap (unordered) * @return {*} no */
void create_min_heap(BinaryHeap *heap)
{
    // Each non-leaf node is adjusted
    for (int i = (heap->length - 2) / 2; i >= 0; i--) { adjust_for_min_heap(heap, i); }}Copy the code

4.2. Insert nodes

You simply insert the new node into the binary heap next to the last node, and then reconstruct the binary heap.

For the minimum heap example, the code is as follows:

/** * @description: Insert an element into the smallest heap * @param {BinaryHeap} *heap smallest heap pointer * @param {int} elem new element * @return {*} None */
void insert_into_min_heap(BinaryHeap *heap, int elem)
{
    if (heap->length == MAXSIZE) {
        printf("The binary heap is full and cannot be inserted. \n");
        return;
    }
    heap->array[heap->length] = elem; / / insert
    heap->length++; // Update the length
    create_min_heap(heap); // re-construct
}
Copy the code

4.3. Delete nodes

Move (assign) the last node to the top of the heap, then reconstruct the binary heap.

For the minimum heap example, the code is as follows:

/** * @description: Remove the heap top of the minimum heap * @param {BinaryHeap} *heap minimum heap pointer * @param {int} *elem save variable pointer * @return {*} None */
void delete_from_min_heap(BinaryHeap *heap, int *elem)
{
    if (heap->length == 0) {
        printf("Binary heap empty, no element to delete. \n");
        return;
    }
    *elem = heap->array[0];
    heap->array[0] = heap->array[heap->length - 1]; // Move to top of heap
    heap->length--; // Update the length
    create_min_heap(heap); // re-construct
}
Copy the code

5. To summarize

The essence of constructing a maximum heap is to float the “big” nodes of each subtree up as parents and sink the “small” nodes down as children.

The essence of constructing a minimal heap is to float the “small” nodes of each subtree as parents and sink the “large” nodes as children.

The essence of insertion node is to insert the new node to the end of binary heap, destroy the structure of the original binary heap, and then adjust the newly obtained complete binary tree to reconstruct the binary heap.

The essence of deleting nodes is to delete the heap top, destroy the structure of the original complete binary tree, and then use the last node to reconstruct the complete binary tree, and then adjust the newly obtained complete binary tree to reconstruct the binary heap.

In four words summed up is – break and then stand.

As for the implementation of the code, the key is to adjust the nodes, understand this, the rest is simple.

So that’s the principle of binary heap and related operations.

Complete code please visit lot | Gitee acquisition.

Please correct me if there are any mistakes.

If you think it’s good, you can like it and follow it. More data structures and algorithms will follow.

【 Recommended reading 】

• Use diagrams and code to make you understand the sequential structure of linear tables
• After reading this article, I finally understand the linked list
• 【 Data structure of the stack 】 With detailed pictures and texts to understand the “stack” (Principle)
• The queue of data structures Learning queues, read this one is enough!
• 【 Data structure linked list 】 detailed graphics teach you tricks to play linked list
• [Data structure of binary tree] to understand the concept and principle of binary tree
• Data structure of binary tree binary tree creation and traversal implementation
• Cue binary trees for data Structures: The principle and creation of cue binary trees