Binary stack (I) - principle and C implementation

Summary

This chapter introduces binary stack , Binary heap is what we usually call data structure " Pile up " One of the . As usual , This article will first give a brief introduction to the theoretical knowledge of binary pile , Then give C The realization of language . We will give you the following C++ and Java Implementation of version ; The language of implementation is different , But the principle is the same , Choose one of them to learn . If there are mistakes or deficiencies in the article , Please point out ！

Catalog
1.  Introduction to heap and binary heap
2.  Graph and text analysis of binary heap
3.  It's two forks C Realization ( Complete source code )
4.  It's two forks C The test program

Reprint please indicate the source ： Binary heap ( One ) And Graphic analysis and C The realization of language - If the sky doesn't die - Blog Garden

---

More ： Data structure and algorithm series Catalog

(01)  Binary heap ( One ) And Graphic analysis and C The realization of language
(02)  Binary heap ( Two ) And C++ The implementation of the
(03)  Binary heap ( 3、 ... and ) And Java Reality of

Introduction to heap and binary heap

The definition of the heap

Pile up (heap), The heap mentioned here is the heap in the data structure , Instead of the heap in the memory model . A heap is usually a tree that can be thought of as a tree , It satisfies the following properties ：
[ Property one ] The value of any node in the heap is always no greater than ( Not less than ) The value of its child nodes ;
[ Property two ] Pile is always a complete tree .
The heap with any node no larger than its child nodes is called the minimum heap or small root heap , The heap with any node no less than its child nodes is called the maximum heap or large root heap . A common pile has two forks 、 Left leaning reactor 、 Slant pile 、 Binomial pile 、 Fibonacci and so on .

The definition of binary heap

Binary heap is a complete binary tree or an approximate complete binary tree , There are two kinds ： The largest heap and the smallest heap .
The biggest pile ： The key value of the parent is always greater than or equal to the key value of any child node ; The smallest pile ： The key value of the parent is always less than or equal to the key value of any child node . The schematic diagram is as follows ：

Binary piles usually pass through " Array " To achieve . Array implementation of binary heap , There is a certain relationship between the position of parent node and child node . occasionally , We will " The first element of a binary stack " Put it in the array index 0 The location of , Sometimes it's on 1 The location of . Of course , They are essentially the same ( It's all binary piles ), There is only a slight difference in implementation .
hypothesis " First element " The index in the array is 0 Words , Then the relationship between the parent node and the child node is as follows ：
(01) The index for i The left child's index is (2*i+1);
(02) The index for i The left child's index is (2*i+2);
(03) The index for i The index of the parent node of is floor((i-1)/2);

hypothesis " First element " The index in the array is 1 Words , Then the relationship between the parent node and the child node is as follows ：
(01) The index for i The left child's index is (2*i);
(02) The index for i The left child's index is (2*i+1);
(03) The index for i The index of the parent node of is floor(i/2);

Be careful ： The implementation of binary heap in this paper adopts " The first element of the binary heap is at the array index 0" The way ！

Graph and text analysis of binary heap

in front , We have learned ：" The biggest pile " and " The smallest pile " It's symmetry . It also means that , Just know one of them . The graphic analysis of this section is based on " The biggest pile " To introduce .

The core of binary stack is " Add a node " and " Delete node ", Understand these two algorithms , Binary stack is basically mastered . Let's introduce them .

1. add to

Suppose at the maximum heap [90,80,70,60,40,30,20,10,50] Species addition 85, The steps to be performed are as follows ：

As shown in the figure above , When adding data to the maximum heap ： First add the data to the end of the largest heap , And then move the element up as much as possible , Until you can't move ！
take 85 Add to [90,80,70,60,40,30,20,10,50] In the after , The largest heap becomes [90,85,70,60,80,30,20,10,50,40].

Insert code of the largest heap (C Language )

/*
 *  Up adjustment algorithm of maximum heap ( from start Start up until 0, Adjust the heap )
 *
 *  notes ： In the heap of array implementation , The first N The index value of the left child of nodes is (2N+1), The child's index is right (2N+2).
 *
 *  Parameter description ：
 *     start --  The starting position of the raised node ( Generally, it is the index of the last element in the array )
 */
static void maxheap_filterup(int start)
{
    int c = start;            //  Current node (current) The location of 
    int p = (c-1)/2;        //  Father (parent) The location of the node  
    int tmp = m_heap[c];        //  Current node (current) Size 

    while(c > 0)
    {
        if(m_heap[p] >= tmp)
            break;
        else
        {
            m_heap[c] = m_heap[p];
            c = p;
            p = (p-1)/2;   
        }       
    }
    m_heap[c] = tmp;
}
  
/* 
 *  take data Insert into the binary stack 
 *
 *  Return value ：
 *     0, It means success 
 *    -1, It means failure 
 */
int maxheap_insert(int data)
{
    //  If " Pile up " Is full , Then return to 
    if(m_size == m_capacity)
        return -1;
 
    m_heap[m_size] = data;        //  take " Array " Insert at the end of the watch 
    maxheap_filterup(m_size);    //  Adjust the reactor upward 
    m_size++;                    //  The actual capacity of the heap +1

    return 0;
}

maxheap_insert(data) The role of ： Put the data data Add to the largest heap .
When the pile is full , Add failure ; otherwise data Add to the end of the maximum heap . Then readjust the array by raising the algorithm , Make it the largest heap again .

2. Delete

Suppose from the maximum heap [90,85,70,60,80,30,20,10,50,40] Delete in 90, The steps to be performed are as follows ：

from [90,85,70,60,80,30,20,10,50,40] Delete 90 after , The largest heap becomes [85,80,70,60,40,30,20,10,50].
As shown in the figure above , When data is deleted from the maximum heap ： Delete the data first , Then insert the empty bit with the last element in the largest heap ; next , Put this “ vacancy ” Try to move up , Until the remaining data becomes a maximum heap .

Be careful ： Consider starting from the maximum heap [90,85,70,60,80,30,20,10,50,40] Delete in 60, The steps performed cannot simply be replaced by its child nodes ; And must take into account " The replaced tree is still the largest heap "！

Delete code of the largest heap (C Language )

/* 
 *  return data Index in binary heap 
 *
 *  Return value ：
 *      There is  --  return data Index in array 
 *      non-existent  -- -1
 */
int get_index(int data)
{
    int i=0;

    for(i=0; i<m_size; i++)
        if (data==m_heap[i])
            return i;

    return -1;
}

/* 
 *  Downward adjustment algorithm of maximum heap 
 *
 *  notes ： In the heap of array implementation , The first N The index value of the left child of nodes is (2N+1), The child's index is right (2N+2).
 *
 *  Parameter description ：
 *     start --  The starting position of the downregulated node ( It's usually 0, Says from the first 1 Start )
 *     end   --  Up to range ( Generally, it is the index of the last element in the array )
 */
static void maxheap_filterdown(int start, int end)
{
    int c = start;          //  At present (current) Location of nodes 
    int l = 2*c + 1;     //  Left (left) The child's position 
    int tmp = m_heap[c];    //  At present (current) The size of the node 

    while(l <= end)
    {
        // "l" The left child. ,"l+1" It's the right child 
        if(l < end && m_heap[l] < m_heap[l+1])
            l++;        //  Choose the older of the left and right children , namely m_heap[l+1]
        if(tmp >= m_heap[l])
            break;        // Adjust the end 
        else
        {
            m_heap[c] = m_heap[l];
            c = l;
            l = 2*l + 1;   
        }       
    }   
    m_heap[c] = tmp;
}

/*
 *  Delete data
 *
 *  Return value ：
 *      0, success 
 *     -1, Failure 
 */
int maxheap_remove(int data)
{
    int index;
    //  If " Pile up " It's empty , Then return to -1
    if(m_size == 0)
        return -1;

    //  obtain data Index in array 
    index = get_index(data); 
    if (index==-1)
        return -1;

    m_heap[index] = m_heap[--m_size];        //  Fill with the last element 
    maxheap_filterdown(index, m_size-1);    //  from index The position is adjusted from top to bottom to the maximum heap 

    return 0;
}

maxheap_remove(data) The role of ： Delete data from the maximum heap data.
When the heap is empty , Delete failed ; Otherwise, investigate and deal with data Position in the maximum heap array . After finding it , First replace the deleted element with the last element ; Then adjust the array again by adjusting the algorithm , Make it the largest heap again .

The " The complete code for the example " as well as " Code related to the smallest heap ", Please refer to the following implementation of binary heap .

It's two forks C Realization ( Complete source code )

The implementation of binary heap also includes " The biggest pile " and " The smallest pile ", They are symmetrical ; Understand a , The other one is very easy to understand .

Binary heap ( The biggest pile ) Implementation file of (max_heap.c)

 View Code

Binary heap ( The smallest pile ) Implementation file of (min_heap.c)

 View Code

It's two forks C The test program

The test program has been included in the corresponding implementation file , I won't repeat it here .

The biggest pile (max_heap.c) Results of operation ：

==  Add... In turn : 10 40 30 60 90 70 20 50 80 
==  most   Big   Pile up : 90 80 70 60 40 30 20 10 50 
==  Additive elements : 85
==  most   Big   Pile up : 90 85 70 60 80 30 20 10 50 40 
==  Remove elements : 90
==  most   Big   Pile up : 85 80 70 60 40 30 20 10 50 

The smallest pile (min_heap.c) Results of operation ：

==  Add... In turn : 80 40 30 60 90 70 10 50 20 
==  most   Small   Pile up : 10 20 30 50 90 70 40 80 60 
==  Additive elements : 15
==  most   Small   Pile up : 10 15 30 50 20 70 40 80 60 90 
==  Remove elements : 10
==  most   Small   Pile up : 15 20 30 50 90 70 40 80 60 

PS.  The binary stack is " Heap sort " Theoretical foundation stone . When I explain the algorithm later, I will explain " Heap sort ", I understand " Binary heap " after ," Heap sort " It's easy .