[Data structure] — The blogger patted you and threw a “heap” binary tree at you (heap concept + structure + code implementation)

3.1 Heap creation:

Below we give an array, which logically can be regarded as a complete binary tree, but it is not a heap yet. Now we use an algorithm to build it into a heap. The left and right subtrees of the root node are not heaps, how do we adjust it? Here we start to adjust from the last subtree of the first non-leaf node to the tree of the root node, and then we can adjust it into a pile.

3.2 Heap structure:

#include<stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{<!-- -->
HPDataType* a;
int size;
int capacity;
}HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

3.3 Initialization:

void HeapInit(HP* php)
{<!-- -->
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}

3.4 Heap insertion:

3.4.1 Heap adjustment algorithm:

To insert data into the heap, you need to use the upward adjustment algorithm to adjust, because inserting data into the heap is to insert the data into the position with the subscript size. At this time, the small heap (large heap) is not satisfied, so the heap needs to be adjusted , the upward adjustment algorithm is similar to the downward adjustment algorithm. Here we take the small heap as an example. The upward adjustment method only needs to start from the position of the inserted node and compare it with the parent node.

3.4.1.1 code (take small heap as an example):

void AdjustUp(HPDataType* a, int child)
{<!-- -->
int parent = (child - 1) / 2;
while (child>0)
{<!-- -->
if (a[child] < a[parent])
{<!-- -->
HPDataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
child = parent;
parent = (child - 1) / 2;
}
else
{<!-- -->
break;
}
}
}

3.4.1.2 Flowchart:

3.4.2 Heap adjustment algorithm (insert):

void HeapPush(HP* php, HPDataType x)
{<!-- -->
assert(php);
if (php->size == php->capacity)
{<!-- -->
int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{<!-- -->
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
AdjustUp(php->a, php->size);//heap upward adjustment algorithm
php->size++;
}

3.5 Deletion of the heap (delete the top element of the heap):

For the deletion of the top element of the heap, coverage may be thought of, but the coverage is obviously not satisfactory because when we delete the top element of the heap, the node that is originally a brother relationship becomes a parent-child relationship, which leads to disordered relationships (once the relationship is disordered, it will lead to dissatisfaction The relationship between parents and offspring in a large pile/small pile-for a small pile, the parent is smaller than the child)
As shown in the picture:

So we found another way: first exchange the top data of the heap and the last data so that the intermediate relationship does not cause confusion, then reduce the number of data, and then adjust the heap after the last data exchange (only need to compare the top element of the heap with the child’s The relationship meets the relationship) – First compare the size relationship between its two children (left child and right child), find the smaller one and then compare it with the top data of the heap. If it is smaller, then exchange and then compare and exchange stop until the subscript of the child >= the number of data.
Pay attention to one point: Maybe it has only left child and no right child, so we have to correct the right child Judging that the subscript of the right child must be smaller than the number of heap data, otherwise it will cross the boundary

3.5.1 Heap adjustment algorithm:

Now we give an array, which is logically regarded as a complete binary tree. We can adjust it into a small heap through the downward adjustment algorithm starting from the root node. The downward adjustment algorithm has a premise: the left and right subtrees must be a heap to be adjusted.

3.5.1.1 code (take small heap as an example):

void AdjustDown(int* a, int n, int parent)
{<!-- -->
int child = parent * 2 + 1;//Assume the left child is small
while (child<n)
{<!-- -->
if (child + 1<n & amp; & amp; a[child + 1] < a[child])
//child + 1<n judges that the subscript of the right child satisfies and does not cross the boundary and then compare
//a[child + 1] < a[child] right child < left child, it means the right child child + + is the right child
{<!-- -->
child ++ ;
}
if (a[child] < a[parent])
{<!-- -->
Swap( &a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{<!-- -->
break;
}
}
}

3.5.1.2 Flowchart:

3.5.2 Heap adjustment algorithm (deleted):

void HeapPop(HP* php)
{<!-- -->
assert(php);
assert(!HeapEmpty(php));
// swap head to tail
Swap( & amp; php->a[0], & amp; php->a [php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}

3.6 Heap top data:

HPDataType HeapTop(HP* php)
{<!-- -->
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}

3.7 The number of heap data in the heap:

int HeapSize(HP* php)
{<!-- -->
assert(php);
return php->size;
}

3.8 Empty judgment:

bool HeapEmpty(HP* php)
{<!-- -->
assert(php);
return php->size == 0;
}

3.9 release:

void HeapDestroy(HP* php)
{<!-- -->
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}

Four, the complete code of heap implementation:

//Heap.h
#include 
#include 
#include 
#include 
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

//Heap.c
#include"Heap.h"
void HeapInit(HP* php)
{<!-- -->
assert(php);
php->a = NULL;
php->size = 0;
php->capacity = 0;
}

void HeapDestroy(HP* php)
{<!-- -->
assert(php);
free(php->a);
php->a = NULL;
php->capacity = php->size = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}

void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child>0)
{
if (a[child] < a[parent])
{
Swap( &a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}

void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
AdjustUp(php->a, php->size);
php->size++;
}

void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child
if (child + 1
child ++ ;
}
if (a[child] < a[parent])
{
Swap( &a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

//delete heap top data
void HeapPop(HP* php)
{<!-- -->
assert(php);
assert(!HeapEmpty(php));
// swap head to tail
Swap( & amp; php->a[0], & amp; php->a [php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}

HPDataType HeapTop(HP*php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}

bool HeapEmpty(HP* php)
{<!-- -->
assert(php);
return php->size == 0;
}

int HeapSize(HP* php)
{<!-- -->
assert(php);
return php->size;
}

//Test.c
#include"Heap.h"
void HPTest()
{
HP hp;
HeapInit( &hp);
int a[] = { 65,100,70,32,50,60 };
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i ++ )
{
HeapPush( &hp, a[i]);
}

while (!HeapEmpty( &hp))
{
int top = HeapTop( &hp);
printf("%d\\
", top);
HeapPop( &hp);
}
}
int main()
{
HPTest();
return 0;
}

Five, foreshadowing:

After the above code is implemented, you will find that the heap we completed is in an orderly order, taking the small heap as an example, which is the next chapter for the heap The application has made a foreshadowing

Summary

Ending, today’s binary tree – the concept of heap + structure + code implementation content is over~, if you want to know more later, just Please pay attention to me, one click and three links~