Data structure: the sequential structure of the binary tree — heap

Friends and fellows, we meet again. In this issue, I will explain to you the relevant knowledge points of binary tree–heap. If you have some inspiration after reading it, please leave your three links. I wish you all the best! All wishes come true!

C language column: C language: from entry to master

Data Structures Column: Data Structures

Personal homepage: stackY,

Directory

Foreword:

1. The concept and structure of the heap

2. Implementation of the heap

2.1 Create a heap

2.2 Initialize the heap

2.3 Insert data into the heap

2.4 Upward Adjustment Algorithm

2.5 Determine whether the heap is empty

2.6 Delete data in the heap

2.7 Downward Adjustment Algorithm

2.8 The number of effective elements, the top element of the heap

2.9 Code Testing

2.10 Complete code

---

Foreword:

Ordinary binary trees are not suitable for storage in arrays, because there may be a lot of wasted space. And Complete Binary Tree is more suitable for sequential structure storage.

In reality, we usually store the heap (a binary tree) in an array of sequential structures. It is important to pay attention to the heap and operating system here
The heap in the address space of the virtual process is two different things, one is a data structure, and the other is a segment of the operating system that manages memory.

1. The concept and structure of the heap

If there is a key set K = {}, store all its elements in a one-dimensional array in the order of complete binary tree, and satisfy: and (i = 0,1,2,3,4,… n-1) are called small heaps or =K_{2*i + 2 }” class=”mathcode” src=”//i2.wp.com/latex.csdn.net/eq?K_{i}>=K_{2*i & amp;plus;2}” > (i = 0,1,2,3,4,…n-1) is called a big heap, the heap with the largest root node is called the largest heap or the big root heap, and the heap with the smallest root node is called the smallest Heap or rootlet pile.

Graphic:

Simply put:

1. Big heap means that each child node is smaller than its parent node, which only stipulates the size relationship between the parent node and the child node, and does not stipulate The relationship between sibling nodes, the size of two sibling nodes is indeterminate.

2. Small heap means that each child node is larger than its parent node, which only stipulates the size relationship between the parent node and the child node, and does not stipulate The relationship between sibling nodes, the size of two sibling nodes is indeterminate.

So the heap is not necessarily ordered.

Heap Properties:

1. The value of a node in the heap is always not greater than or not less than the value of its parent node.

2. The heap is always a complete binary tree.

2. Implementation of the heap

The heap is a special complete binary tree, so the idea of implementing the heap is to use the sequence table. Similarly, we also write it in modules, creating the header file: Heap.h, source files: Heap.c and Test.c, and the heap is here The main implemented interfaces are: initialization, insertion, deletion (delete heap top element), empty judgment, number of valid elements, heap top element, and destruction. Without further ado, let’s start directly:

Note: What is implemented here is a small heap as an example

2.1 Create a heap

The creation of a heap is to create a sequence table, and then perform a series of operations on the heap:

Header file: Heap.h

//Create heap
//sequence table
typedef int HPDataType;

typedef struct Heap
{
HPDataType* a;
int size = 0; // number of effective elements
int capacity; //capacity
}Heap;

2.2 Initializing the heap

The implementation of these interfaces is relatively simple, just get started:

Header file: Heap.h

//initialization
void HeapInit(Heap* php);

Source file: Heap.c

//initialization
void HeapInit(Heap* php)
{
php->a = NULL;
php->size = 0;
php->capacity = 0;
}

2.3 Insert data into the heap

The insertion heap is inserted at the end of the heap, which corresponds to the last position of the sequence table. After inserting it, there is still a problem: we create a small heap, so if the inserted data is smaller than its father, it will be It needs to be adjusted upwards. If it is still smaller than its new father after the adjustment, then it must continue to be adjusted upwards until it conforms to the logic of the small root pile

Therefore, the insertion process can be divided into several steps:

1. First open up a space for the heap.

2. The detection capacity is not enough and needs to be expanded.

3. Insert to determine if upward adjustment is required.

Header file: Heap.h

//insert
void HeapPush(Heap* php, HPDataType x);

Source file: Heap.c

//insert
void HeapPush(Heap* php, HPDataType x)
{
assert(php);
//The process of inserting data
// If the capacity is not enough, it needs to be expanded
// Check if space is insufficient
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
// create space for the heap
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->capacity = newcapacity;
php->a = tmp;
}
//insert data
php->a[php->size] = x;
php->size++;
// adjust up
AdjustUp(php->a, php->size - 1);
}

To adjust the algorithm upwards, let’s repackage a function

2.4 Upward adjustment algorithm

To adjust upwards, our first step is to first find its parent node (under the logic of the sequence table: if it is the left child, then the subscript of its parent node is its subscript -1 Then divide by 2, if it is the right child, then the subscript of its parent node is its subscript -2 and then divide by 2, but what? We are doing integer division, there is no remainder, so whether it is the left child or the right child They are all calculated by dividing -1 by 2). The second step is to judge whether the child is smaller than the father. If it is smaller, the child and the father will exchange positions. If it is larger, it means that it conforms to the logic of the small pile. Just jump out, and then make the parent node after the exchange become a new node. The child node, and then find the new parent node, and so on, until it is adjusted to the top of the heap, and the subscript of the top element is 0, then it means that when the subscript of the child node is 0, there is no need to adjust it, and the exit is Can:

So the relationship between child and father can be summarized as:

int Child = Parent*2 + 1; //left child
int Child = Parent*2 + 2; //right child
int Parent = (Child-1)/2; //father

Source file: Heap.c

//exchange function
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//Adjust the algorithm upwards
void AdjustUp(HPDataType* a, int child)
{
// parent node
int parent = (child - 1) / 2;
// swap up
while (child > 0)
{
/ / Determine the size relationship between parent and child
if (a[child] < a[parent])
{
\t\t\t//exchange
Swap( &a[child], &a[parent]);
//Update parent-child relationship
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}

2.5 Judging whether the heap is empty

The condition for the heap to be empty is that the number of valid elements in the heap is 0.

Header file: Heap.h

//judgment empty
bool HeapEmpty(Heap* php);

Source file: Heap.c

//judgment empty
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}

2.6 Delete data in the heap

When deleting a heap element, the last element is not deleted, so the deletion is meaningless, so when deleting an element in the heap, the element at the top of the heap is deleted, so here are two methods:

1. Like deleting the header of the sequence table, directly move the data to overwrite, but the time complexity is high, and moving the data is a relatively expensive thing, and if the data is moved to overwrite, the original The father-son relationship is disrupted, and the father-son relationship is disrupted, which is a bit nonsense.

2. Exchange the data at the top of the heap with the last data, then delete the last data, and then adjust the remaining elements downward.

So deleting data can be divided into these steps:

1. First judge whether the heap is empty, if it is empty, it cannot be deleted.

2. Swap the top and last data again.

3. Delete the last element again.

4. Then judge whether downward adjustment is required.

Header file: Heap.h

//delete
void HeapPop(Heap* php);

Source file: Heap.c

void HeapPop(Heap* php)
{
assert(php);
// Check if the heap is empty
assert(!HeapEmpty(php));
//Exchange the data at the top of the heap and the last data
Swap( &php->a[0], &php->a[php->size - 1]);
//delete the last data
php->size--;
//Adjust down
AdjustDown(php->a, php->size, 0);
}

To adjust the algorithm downwards, let’s repackage a function

2.7 Downward adjustment algorithm

Downward adjustment algorithm First, we need to find the left and right children of the heap top element according to the subscript relationship between the child and the father, and then find the smallest child among the left and right children, then exchange them, and then update the position of the child to the parent node, and then Continue to find the smallest node of the left and right children of the new parent node, and then exchange, and so on, until the last child node is exchanged (child node is less than or equal to the number of summary points).

To find the smallest of the left and right children, we can use the hypothesis method, assuming that the left child is the smallest, and then make a judgment. If it is not suitable, add 1 to the left child to get the right child. Here we need to pay attention, if there is no right child? ? Then it can only be compared with the left child, and there is no need to compare (Left child plus one is less than or equal to the number of summary points).

Therefore, when we set the downward adjustment algorithm, we need to pass the heap, the number of elements, and the subscript of the top of the heap.

Source file: Heap.c

//Adjust down
void AdjustDown(HPDataType* a, int n, int parent)
{
//Assume the left child is the smallest node among the left and right children
int child = parent * 2 + 1;
\t
while (child < n) // stop when the last child node is swapped
{
if ( child + 1 < n // determine whether there is a right child
& amp; & amp; a[child + 1] < a[child]) //Determine whether the hypothetical left child is the youngest child
{
child + + ; //If it does not match, it will be transformed into the right child
}
//Determine the size relationship between the child and the father
if (a[child] < a[parent])
{
Swap( &a[child], &a[parent]);
//Update parent and child nodes
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

Note:

1. The upward adjustment algorithm and downward adjustment algorithm here are only applicable to the operation of the heap.

2. The time complexity of the upward adjustment algorithm and the downward adjustment algorithm is O(logN).

The best case of upward adjustment and downward adjustment is no adjustment at all, and the worst case is to adjust the height of a complete binary tree times, and because the number of nodes of a complete binary tree is a range [ 2^(h- 1), 2^h-1]. Therefore, combining the height with h and the number of nodes N can calculate the height as [logN + 1, log(N + 1)], so the time complexity of the algorithm is O(logN).

2.8 The number of effective elements, the top element of the heap

1. When returning the top element of the heap, it is first necessary to determine whether the heap is empty. The subscript of the top element is 0, so the element with the subscript 0 is returned directly.

2. The number of valid elements is the size in the sequence table, just return it directly.

Header file: Heap.h

//Number of valid elements
int HeapSize(Heap* php);

//Get the top element of the heap
HPDataType HeapTop(Heap* php);

Source file: Heap.c

//Number of valid elements
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}

//Get the top element of the heap
HPDataType HeapTop (Heap* php)
{
assert(php);
// Check if the heap is empty
assert(!HeapEmpty(php));
return php->a[0];
}

2.9 Code Test

Insert test:

After writing the basic interface of the heap, we can debug and observe through the monitoring window. We insert a piece of data into the heap one by one to observe their changes:

Source file: Test.c

#include "Heap.h"

void HeapTest()
{
Heap hp;

//initialization
HeapInit( &hp);

//insert
int arr[] = { 8,5,6,2,1,0,3,4,7,9 };
for (int i = 0; i < sizeof(arr) / sizeof(int); i ++ )
{
HeapPush( &hp, arr[i]);
}

}

int main()
{
HeapTest();
return 0;
}

Delete test:

#include "Heap.h"

void HeapTest()
{
Heap hp;

//initialization
HeapInit( &hp);

//insert
int arr[] = { 8,5,6,2,1,0,3,4,7,9 };
for (int i = 0; i < sizeof(arr) / sizeof(int); i ++ )
{
HeapPush( &hp, arr[i]);
}

\t//delete
HeapPop( &hp);

}

int main()
{
HeapTest();
return 0;
}

2.10 Complete Code

Header file: Heap.h

#pragma once

// heap

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

// create heap
//sequence table
typedef int HPDataType;

typedef struct Heap
{
HPDataType* a;
int size; //number of effective elements
int capacity; //capacity
}Heap;

//initialization
void HeapInit(Heap* php);

//destroy
void HeapDestroy(Heap* php);

//insert
void HeapPush(Heap* php, HPDataType x);

//delete
void HeapPop(Heap* php);

//judgment empty
bool HeapEmpty(Heap* php);

//Number of valid elements
int HeapSize(Heap* php);

//Get the top element of the heap
HPDataType HeapTop(Heap* php);

Source file: Heap.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

//initialization
void HeapInit(Heap* php)
{
php->a = NULL;
php->size = 0;
php->capacity = 0;
}

//destroy
void HeapDestroy(Heap* php)
{
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}

//exchange function
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//Adjust the algorithm upwards
void AdjustUp(HPDataType* a, int child)
{
// parent node
int parent = (child - 1) / 2;
// swap up
while (child > 0)
{
/ / Determine the size relationship between parent and child
if (a[child] < a[parent])
{
\t\t\t//exchange
Swap( &a[child], &a[parent]);
//Update parent-child relationship
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}

//insert
void HeapPush(Heap* php, HPDataType x)
{
assert(php);
//The process of inserting data
// If the capacity is not enough, it needs to be expanded
// Check if space is insufficient
if (php->size == php->capacity)
{
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
// create space for the heap
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->capacity = newcapacity;
php->a = tmp;
}
//insert data
php->a[php->size] = x;
php->size++;
// adjust up
AdjustUp(php->a, php->size - 1);
}

//Adjust down
void AdjustDown(HPDataType* a, int n, int parent)
{
//Assume the left child is the smallest node among the left and right children
int child = parent * 2 + 1;
\t
while (child < n) // stop when the last child node is swapped
{
if ( child + 1 < n // determine whether there is a right child
& amp; & amp; a[child + 1] < a[child]) //Determine whether the hypothetical left child is the youngest child
{
child + + ; //If it does not match, it will be transformed into the right child
}
//Determine the size relationship between the child and the father
if (a[child] < a[parent])
{
Swap( &a[child], &a[parent]);
//Update parent and child nodes
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

//delete
void HeapPop(Heap* php)
{
assert(php);
// Check if the heap is empty
assert(!HeapEmpty(php));
//Exchange the data at the top of the heap and the last data
Swap( &php->a[0], &php->a[php->size - 1]);
//delete the last data
php->size--;
//Adjust down
AdjustDown(php->a, php->size, 0);
}


//judgment empty
bool HeapEmpty(Heap* php)
{
assert(php);
return php->size == 0;
}

//Number of valid elements
int HeapSize(Heap* php)
{
assert(php);
return php->size;
}

//Get the top element of the heap
HPDataType HeapTop (Heap* php)
{
assert(php);
// Check if the heap is empty
assert(!HeapEmpty(php));
return php->a[0];
}

Source file: Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

void HeapTest()
{
Heap hp;

//initialization
HeapInit( &hp);

//insert
int arr[] = { 8,5,6,2,1,0,3,4,7,9 };
for (int i = 0; i < sizeof(arr) / sizeof(int); i ++ )
{
HeapPush( &hp, arr[i]);
}

\t//delete
//HeapPop( &hp);

}

int main()
{
HeapTest();
return 0;
}

Friends and fellows, the good times are always short-lived. This is the end of our sharing in this issue. Don’t forget to leave your precious three-link after reading it. Thank you for your support!