Data structure – binary tree (2)

(2), Derived data structure – Heap:

Ordinary binary trees are not suitable for storage in arrays because there may be a lot of wasted space. A complete binary tree is more suitable for sequential structure storage. In reality, we usually use heaps
(
A binary tree
)
Use an array of sequential structure for storage. You need to pay attention to the heap and operating system here
The heap in the virtual process address space is two different things. One is a data structure, and the other is an area segmentation that manages memory in the operating system.

1. The concept of heap

The heap is a non-linear structure and a special complete binary tree, so it is suitable for array storage;

2. Classification of heap:

Small heap (small root heap): The value of any parent in the tree is less than or equal to its children;

Big pile (big root pile): The value of any father in the tree is greater than or equal to its children;

As shown below:

(3), Implementation of Heap (Sequential Storage)

Generally, we use the sequential storage method to implement the heap, that is, use a one-dimensional array, so the definition is similar to the sequential table, but the implementation logic is different, so the basic definition and destruction operations will be roughly explained.

1. Definition of heap:

typedef int HPDatatype;
typedef struct Heap
{
HPDatatype* a;//One-dimensional array
int size;//Number of existing elements
int capacity;//Maximum space of current structure
}HP;

2. Heap initialization:

//Initialization
void HPinit(HP* php)
{
assert(php);
php->size = 0;
php->capacity = 0;
php->a = NULL;
}

3. Heap destruction

//Destroy
void HPDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}

4. Heap printing:

//Print
void HPprint(HP* php)
{
assert(php);
for (int i = 0; i < php->size; i + + )
{
printf("%d ", php->a[i]);
}
printf("\
");
}

5.Insert data:

Because the heap is a special complete binary tree, the insertion algorithm is completely different from that of the sequential table;

Let’s take implementing a small heap as an example:

①: First of all, we should consider whether the stack is full. According to our definition, the stack is full when size==capacity. At this time, we need to expand the capacity, because expansion is only possible here, so there is no need to separate it into one The functions and expansion methods are similar in structure to the previous sequence tables, etc., so I won’t explain them too much;

②: According to the sequential storage structure of a complete binary tree, we know that the tail element of the array is the tail element of the complete binary tree, so when we insert data, we only need to insert it at the end of the array, and because the heap is a special complete binary tree, a small heap That is, the value of the parent node is smaller than the value of all its children, so when the data is inserted, the data must be compared with its parents. If the conditions are not met, we need to exchange the data, and we need to perform this operation in a loop. Until the root node is compared, and because we are constantly looking for parents, we call this method “Upward adjustment“. The premise of upward adjustment is that the previous structure is already a heap structure.

③: Since we are looking for parents, we need to keep in mind the previous positional relationship between the parent node and the child node, which is the properties of the above-mentioned complete binary trees. The specific algorithm for upward adjustment is as follows:

④: The time complexity is O(log n with base 2), because the time complexity of inserting elements is O(1), and the worst case of upward adjustment is to adjust to the root node. That is, the height of a complete binary tree is log n with base 2;

⑤, source code

//Exchange function
void Swap(HPDatatype* p1, HPDatatype* p2)
{
HPDatatype tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

//Adjust upward
void AdjustUp(HPDatatype* a, int child)
{
int parent = (child - 1) / 2;

while (child > 0)
{
//Insert data using a small heap as an example
if (a[parent] > a[child])
{
//Swap positions
Swap( & amp;a[parent], & amp;a[child]);
//Reposition and adjust upward after comparing a group
child = parent;
parent = (parent - 1) / 2;
}
else
{
//End of insertion
break;
}
}
}

//insert element
void HPPush(HP* php, HPDatatype x)
{
assert(php);
//expansion
if (php->size == php->capacity)
{
php->capacity = (php->capacity == 0 ? 4 : php->capacity * 2);
HPDatatype* tmp = (HPDatatype*)realloc(php->a, sizeof(HPDatatype) * php->capacity);
//Check expansion
if (tmp == NULL)
{
perror("realloc");
return;
}
php->a = tmp;
}
\t

//insert element
php->a[php->size] = x;
//Check if upward adjustment is needed
AdjustUp(php->a, php->size);
php->size + + ;
}

6.Delete data: