Article directory
- Introduction to Heap
-
- heap concept
- heap structure
- heap adjustment algorithm
-
- The time complexity of building a heap
- Heap Upscaling Algorithm
- The basic function realization of the heap
-
- initialize the heap
- print stack
- heap insertion
- heap deletion
- Get the data at the top of the heap
- Get the number of data in the heap
- empty heap
- destroy heap
Introduction to the heap
The concept of heap
Heap: If there is a key set K={k0,k1,k2,…,kn-1}, store all its elements in a one-dimensional array in the order of a complete binary tree , and satisfy ki<=k2i + 1 and ki<=k2i + 2 (or satisfy ki>=k2i + 1 and ki>=k2i + 2), where i=0,1,2,…, then the set is called for the heap.
Small heap: The heap with the smallest root node is called a small heap, also called a minimum heap or a small root heap.
Big heap: The heap with the largest root node is called a big heap, also called the largest heap or the big root heap.
Nature of the heap:
?The value of a node in the heap is always not greater than or not less than the value of its parent node.
?The heap is always a complete binary tree.
The structure of the heap
Heap adjustment algorithm
Now we are given an array, 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.
However, there is a prerequisite for using the downward adjustment algorithm:
?If you want to adjust it to a small heap, then the left and right subtrees of the root node must both be small heaps.
?If you want to adjust it to a large heap, then the left and right subtrees of the root node must both be large heaps.
?
The basic idea of downward adjustment algorithm (take building a small heap as an example):
?1. Starting from the root node, select the child with the smaller median value of the left and right children.
2. Let the younger child compare with his father.
? If the youngest child is younger than the father, the child’s position is exchanged with that of the father. And take the position of the original young child as the father and continue to adjust downward until it reaches the leaf node.
?If the younger child is older than the father, there is no need to deal with it. After the adjustment is completed, the whole tree is already a small pile.
?
Code example:
//exchange function
void Swap(int* x, int* y)
{<!-- -->
int tmp = *x;
*x = *y;
*y = tmp;
}
//The downward adjustment of the heap (small heap)
void AdjustDown(int* a, int n, int parent)
{<!-- -->
//child records the subscript of the child with the smaller value among the left and right children
int child = 2 * parent + 1;//First, the value of the left child is smaller by default
while (child < n)
{<!-- -->
if (child + 1 < n & amp; & amp; a[child + 1] < a[child])//the right child exists and the right child is smaller than the left child
{<!-- -->
child + + ;//The smaller child is changed to the right child
}
if (a[child] < a[parent])//The value of the smaller child among the left and right children is smaller than the parent node
{<!-- -->
// Swap the parent node with the smaller child node
Swap( &a[child], &a[parent]);
//Continue to adjust downward
parent = child;
child = 2 * parent + 1;
}
else//has piled up
{<!-- -->
break;
}
}
}
Use the downward adjustment algorithm of the heap (adjust once), in the worst case (that is, always need to exchange nodes), the number of cycles required is: h – 1 times (h is the height of the tree) . And h = log2(N + 1) (N is the number of summary points of the tree). So the time complexity of the downward adjustment algorithm of the heap is: O(logN).
As mentioned above, using the downward adjustment algorithm of the heap needs to satisfy that the left and right subtrees of the root node are both large heaps or small heaps, so how can a arbitrary tree be adjusted into a heap? ?
?The answer is very simple, we only need to start from the last non-leaf node, from the back to the front, press the subscript, and then use it as the root to adjust downwards.
?
Code example:
// build heap
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{<!-- -->
AdjustDown(php->a, php->size, i);
}
Time complexity of building a heap
So what is the time complexity of building a heap?
?When the number of nodes is infinite, the difference between a complete binary tree and a full binary tree with the same number of layers is negligible. Therefore, when calculating the time complexity, we can regard a complete binary tree as a full binary tree with the same number of layers. Binary tree for calculation.
?
To summarize:
The time complexity of the downward adjustment algorithm of the heap: T ( n ) = O ( log ? N ) T(n)=O(\log N)T(n)=O(logN).
The time complexity of building a heap: T ( n ) = O ( N ) T(n)=O(N)T(n)=O(N).
Heap adjustment algorithm
When we insert a piece of data at the end of a heap, we need to adjust the heap so that it is still a heap. At this time, we need to use the upward adjustment algorithm of the heap.
Basic idea of upward adjustment algorithm (take building a small heap as an example):
?1. Compare the target node with its parent node.
?2. If the value of the target node is smaller than the value of its parent node, exchange the positions of the target node and its parent node, and use the parent node of the original target node as the new target node to continue upward Adjustment. If the value of the target node is greater than the value of its parent node, stop the upward adjustment, and the tree is already a small heap at this time.
?
Code example:
//exchange function
void Swap(HPDataType* x, HPDataType* y)
{<!-- -->
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
//Up adjustment of the heap (small heap)
void AdjustUp(HPDataType* a, int child)
{<!-- -->
int parent = (child - 1) / 2;
while (child > 0)//Adjust to the position of the root node
{<!-- -->
if (a[child] < a[parent])//The value of the child node is less than the value of the parent node
{<!-- -->
//Swap the parent node with the child node
Swap( &a[child], &a[parent]);
//Continue to adjust upwards
child = parent;
parent = (child - 1) / 2;
}
else//has piled up
{<!-- -->
break;
}
}
}
Basic function implementation of the heap
Initialize the heap
First, a heap type must be created, which must contain the basic information of the heap: the array for storing data, the number of elements in the heap, and the maximum capacity of the current heap.
typedef int HPDataType;//The type of data stored in the heap
typedef struct Heap
{<!-- -->
HPDataType* a;//Array for storing data
int size;//Record the number of elements in the heap
int capacity;//Record the capacity of the heap
}HP;
Then we need an initialization function to initialize the newly created heap. Note that the incoming data must be built during initialization.
//Initialize the heap
void HeapInit(HP* php, HPDataType* a, int n)
{<!-- -->
assert(php);
HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType)*n);//Apply for a heap structure
if (tmp == NULL)
{<!-- -->
printf("malloc fail\\
");
exit(-1);
}
php->a = tmp;
memcpy(php->a, a, sizeof(HPDataType)*n);//Copy data to the heap
php->size = n;
php->capacity = n;
int i = 0;
// build heap
for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
{<!-- -->
AdjustDown(php->a, php->size, i);
}
}
Print heap
Print the data in the heap. Here, two printing formats are used.
The first printing format is to print according to the physical structure of the heap, that is, to print as a row of continuous numbers.
The second printing format is to print according to the logical structure of the heap, that is, to print in a tree structure.
//Find the depth of a binary tree with n nodes
int depth(int n)
{<!-- -->
assert(n >= 0);
if (n>0)
{<!-- -->
int m = 2;
int height = 1;
while (m < n + 1)
{<!-- -->
m *= 2;
hight + + ;
}
return hight;
}
else
{<!-- -->
return 0;
}
}
// print heap
void HeapPrint(HP* php)
{<!-- -->
assert(php);
//Print according to the physical structure
int i = 0;
for (i = 0; i < php->size; i + + )
{<!-- -->
printf("%d ", php->a[i]);
}
printf("\\
");
//Print according to the tree structure
int h = depth(php->size);
int N = (int)pow(2, h) - 1;//The total number of nodes in the full binary tree with the same depth as the binary tree
int space = N - 1;//Record the number of spaces in front of each line
int row = 1;//The number of rows currently printed
int pos = 0;//subscript of the data to be printed
while (1)
{<!-- -->
// print the leading space
int i = 0;
for (i = 0; i < space; i ++ )
{<!-- -->
printf(" ");
}
// print data and spacing
int count = (int)pow(2, row - 1);//number of numbers in each row
while (count--)//print a line
{<!-- -->
printf(" d", php->a[pos + + ]);//print data
if (pos >= php->size)//The data is printed
{<!-- -->
printf("\\
");
return;
}
int distance = (space + 1) * 2;//the number of spaces between two numbers
while (distance--)//print the space between two numbers
{<!-- -->
printf(" ");
}
}
printf("\\
");
row + + ;
space = space / 2 - 1;
}
}
Heap insertion
When data is inserted, it is inserted at the end of the array, that is, the last node of the last layer of the tree structure, so after inserting data, we need to use the upward adjustment algorithm of the heap to adjust the heap so that it still maintains the heap after inserting data Structure.
//heap insertion
void HeapPush(HP* php, HPDataType x)
{<!-- -->
assert(php);
if (php->size == php->capacity)
{<!-- -->
HPDataType* tmp = (HPDataType*)realloc(php->a, 2 * php->capacity*sizeof(HPDataType));
if (tmp == NULL)
{<!-- -->
printf("realloc fail\\
");
exit(-1);
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
// adjust up
AdjustUp(php->a, php->size - 1);
}
Heap deletion
The deletion of the heap deletes the elements at the top of the heap, but this deletion process does not directly delete the data at the top of the heap, but first exchanges the data at the top of the heap with the position of the last node, and then deletes the last node , and make another downward adjustment to the heap.
?Reason: If we directly delete the data at the top of the heap, then the parent-child relationship of the data behind the original heap will be disrupted, and the whole heap needs to be rebuilt. The time complexity is O ( N ) O(N)O(N). If the above method is used, then only one downward adjustment of the heap is required, because at this time the left and right subtrees of the root node are all small heaps, and we only need to perform one downward adjustment at the root node. The complexity is: O(log(N)).
//heap deletion
void HeapPop(HP* php)
{<!-- -->
assert(php);
assert(!HeapEmpty(php));
Swap( & amp;php->a[0], & amp;php->a[php->size - 1]);//Exchange the position of the top and last node of the heap
php->size--;//Delete the last node (that is, delete the element at the top of the original heap)
AdjustDown(php->a, php->size, 0);//Adjust down
}
Get the data at the top of the heap
Get the data at the top of the heap, that is, return the data with the subscript 0 in the array.
//Get the data at the top of the heap
HPDataType HeapTop(HP*php)
{<!-- -->
assert(php);
assert(!HeapEmpty(php));
return php->a[0];//return the heap top data
}
Get the number of data in the heap
Get the number of data in the heap, that is, return the size variable in the heap structure.
//Get the number of data in the heap
int HeapSize(HP* php)
{<!-- -->
assert(php);
return php->size;//return the number of data in the heap
}
Empty judgment of the heap
The empty judgment of the heap is to judge whether the size variable in the heap structure is 0.
//Judging empty heap
bool HeapEmpty(HP* php)
{<!-- -->
assert(php);
return php->size == 0;//judging whether the data in the heap is 0
}
Destroy the heap
In order to avoid memory leaks, the dynamically opened memory space must be released in time after using it. Therefore, a function for releasing memory space is essential.
//Destroy the heap
void HeapDestroy(HP* php)
{<!-- -->
assert(php);
free(php->a);//Release the dynamically opened array
php->a = NULL;//empty in time
php->size = 0;//Set the number of elements to 0
php->capacity = 0;//set the capacity to 0
}