Introduction to heap
The heap uses an array to store a complete binary tree. Generally, a sequence table is used to implement the heap data structure.
Properties of the heap:
- The value of a node in the heap is always no greater than (large heap) or no less than (small heap) the value of its parent node
- The heap is a complete binary tree
Small heap: The value of the left and right nodes must be greater than or equal to the value of its parent node
Big pile: The value of the left and right nodes must be less than or equal to the value of its parent node
Downward adjustment of the heap:
Now we are given an array, which is logically regarded as a complete binary tree. We can adjust it through the downward adjustment algorithm starting from the root node
Adjust prerequisites downward:
If you want to adjust the small heap to the left and right subtrees, it must be a small heap
If you want to adjust the big heap to the left and right subtrees, they must be big heaps
Adjust your thoughts downward: (Take a big pile as an example)
1. Start from the root node and find the larger value of the left and right children
2. Let the older child compare with his father
If the older child is older than the father, exchange the positions of the child node and the father node, and continue to use the position of the original larger child as the father, and adjust downward until the leaf node
If the value of the child node is not greater than the value of the parent node, it means that the big pile has been built.
code show as below:
//A large pile is taken as an example
void AdjustDown(HPDataType* a, int size, int parent)
{
//Assume that the left child is the older of the two children
int child = parent * 2 + 1;
//The subscript of child must be within the valid subscript of the array
while (child < size)
{
//prevent crossing the boundary
if ((child + 1 < size) & amp; & amp; a[child + 1] > a[child]) // If the right child is larger than the left child, change child to right child
{
//The elements in the array are consecutive, so the left child + 1 is the right child
+ + child; //
}
if (a[child] > a[parent])
{
Swap( & amp;a[child], & amp;a[parent]); //If the child is larger than the father, swap the positions of the child and the father.
//iterate--
parent = child; //update parent
child = parent * 2 + 1; //Update child
}
else
{
//Heap is completed
break;
}
}
}
How to build a pile of any tree
As mentioned before, using heap to adjust downward requires that the left and right subtrees of the root are (large or small heap). Find the last non-leaf node and start adjusting downward.
code show as below:
for (int i = (n - 1 - 1) / 2; i >=0; i--)
{
AdjustDown(arr, n, i);
}
Heap adjustment upward
Insert a piece of data at the end of the heap and adjust it upward so that the heap structure still meets the large heap conditions.
Adjust your thoughts upward: (Take Dadu as an example)
1. Find its parent (child-1)/2 through the subscript just inserted
2. Compare the value of the child node with the value of the parent node
If the value of the child node is greater than the value of the parent node, exchange their positions, and use the position of the original parent node as the new child. Then find the father through the child and continue to adjust upward until the root node.
3. If the value of the child node is not greater than the value of the parent node, it means that the big pile has been built.
code show as below:
//Jian Da Dui Adjust upward
void AdjustUpward(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
//If the child's value is greater than the parent's value, swap the positions of the child and parent.
Swap( & amp;a[child], & amp;a[parent]);
// iterate --
child = parent; //update child
parent = (child - 1) / 2; //update parent
}
else
{
//Heap is completed
break;
}
}
}
Adjust prerequisites upward:
- If you want to adjust the small heap to the left and right subtrees, it must be a small heap
- If you want to adjust the big heap to the left and right subtrees, they must be big heaps
Implementation of heap
The following implements the functions of the heap. The key points are the push and pop of the heap.
//Initialization of heap void HeapInit(Heap* hp); //Heap destruction void HeapDestroy(Heap* hp); // why is push instead of BackPush or frontPush because heap insertion may be inserted anywhere, front, middle or back. //Insertion into the heap void HeapPush(Heap* hp, HPDataType x); //To make deletion more meaningful, delete the data at the top here void HeapPop(Heap* hp); //Get the data at the top of the heap HPDataType HeapTTop(Heap* hp); //Get the number of valid data in the heap int HeapSize(Heap* hp); //Determine whether the heap is empty bool HeapEmpty(Heap* hp); //Already have a large pile as an example void AdjustDown(HPDataType* a, int size, int parent); //Build a big pile and adjust upward void AdjustUpward(HPDataType* a, int child); //exchange function void Swap(HPDataType* p1, HPDataType* p2);
The logical structure of the heap is a complete binary tree //imagined
The physical structure of the heap is stored in an array, so a sequence table is used to implement the heap.
//The logical structure of the heap is a complete binary tree //imagined
//The physical structure of the heap stores the array
//So use sequence table to implement heap
typedef int HPDataType;
typedef struct HeapNode
{
HPDataType* a; //Points to a dynamically opened space
int size; //Number of valid data
int capacity;//effective capacity size
}Heap;
Heap initialization
void HeapInit(Heap* hp)
{
// hp->a points to a dynamically opened space
hp->a = (HPDataType*)malloc(sizeof(HPDataType) * 6);
if (hp->a == NULL)
{
perror("malloc:");
exit(-1);
}
hp->size = 0;
hp->capacity = 6; //The effective space capacity is first given as 6
}
Heap destruction
Release the space requested by dynamic memory and clear the variables.
//Heap destruction
void HeapDestroy(Heap* hp)
{
free(hp->a);//Release the space requested by dynamic memory
hp->a = NULL; // Leave blank
hp->size = 0; //Clear
hp->capacity = 0;clear
}
Heap insertion
Why is push instead of BackPush or frontPush? Because the heap structure will not be destroyed after heap insertion. It is possible to insert it anywhere, front, middle or back.
//Insertion into the heap
void HeapPush(Heap* hp, HPDataType x)
{
// If there is not enough space, expand it.
if (hp->size == hp->capacity)
{
HPDataType* tmp =(HPDataType*)realloc(hp->a, sizeof(HPDataType) * hp->capacity * 2);
if (tmp == NULL)
{
perror("reallco:");
exit(-1);
}
\t\t
// Expansion may occur: in-situ expansion off-site expansion
\t\t//so
hp->a = tmp;
hp->capacity *= 2;
}
hp->a[hp->size + + ] = x;
//size -1 is the subscript of the last element
AdjustUpward(hp->a, hp->size-1);
}
//exchange function
void Swap(HPDataType* p1, HPDataType* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//Build a big pile and adjust upward
void AdjustUpward(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
//If the child's value is greater than the parent's value, swap the positions of the child and parent.
Swap( & amp;a[child], & amp;a[parent]);
// iterate --
child = parent; //update child
parent = (child - 1) / 2; //update parent
}
else
{
//Heap is completed
break;
}
}
}
Heap deletion
To make deletion more meaningful here delete the data at the top
In order not to destroy the heap structure
1 First exchange the top element with the last element
2 Delete the last element (the top element at this time)
3 Adjust downward until a large number of conditions are met
void HeapPop(Heap* hp)
{
assert(hp);
//You need to have data in the data heap if you want to delete it
assert(hp->size > 0);
//1 First exchange the top element with the last element
Swap( & amp;hp->a[0], & amp;hp->a[hp->size - 1]);
hp->size--; //Delete the last element (the top element is deleted at this time)
//Adjust downward
AdjustDown(hp->a, hp->size, 0);
}
//exchange function
void Swap(HPDataType* p1, HPDataType* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//Build a big pile and adjust upward
void AdjustUpward(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
//If the child's value is greater than the parent's value, swap the positions of the child and parent.
Swap( & amp;a[child], & amp;a[parent]);
// iterate --
child = parent; //update child
parent = (child - 1) / 2; //update parent
}
else
{
//Heap is completed
break;
}
}
}
Get the data at the top of the heap
Subscript 0 is the data at the top of the heap
HPDataType HeapTTop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
return hp->a[0];
}
Get the number of valid data in the heap
It is the number of size
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
Determine whether the heap is empty
Here, the judgment condition for the heap to be empty is hp->size == 0
bool HeapEmpty(Heap* hp)
{
return hp->size == 0;
}
Overall code implementation
Heap.h
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//The logical structure of the heap is a complete binary tree //Imaginary
//The physical structure of the heap stores the array
//So use sequence table to implement heap
typedef int HPDataType;
typedef struct HeapNode
{
HPDataType* a; //Points to a dynamically opened space
int size; //Number of valid data
int capacity;//effective capacity size
}Heap;
//Initialization of heap
void HeapInit(Heap* hp);
//Heap destruction
void HeapDestroy(Heap* hp);
// why is push instead of BackPush or frontPush because heap insertion may be inserted anywhere, front, middle or back.
//Insertion into the heap
void HeapPush(Heap* hp, HPDataType x);
//To make deletion more meaningful, delete the data at the top here
void HeapPop(Heap* hp);
//Get the data at the top of the heap
HPDataType HeapTTop(Heap* hp);
//Get the number of valid data in the heap
int HeapSize(Heap* hp);
//Determine whether the heap is empty
bool HeapEmpty(Heap* hp);
//Already have a large pile as an example
void AdjustDown(HPDataType* a, int size, int parent);
//Build a big pile and adjust upward
void AdjustUpward(HPDataType* a, int child);
//exchange function
void Swap(HPDataType* p1, HPDataType* p2);
Heap.c
//Initialization of heap
void HeapInit(Heap* hp)
{
// hp->a points to a dynamically opened space
hp->a = (HPDataType*)malloc(sizeof(HPDataType) * 6);
if (hp->a == NULL)
{
perror("malloc:");
exit(-1);
}
hp->size = 0;
hp->capacity = 6; //The effective space capacity is first given as 6
}
//Heap destruction
void HeapDestroy(Heap* hp)
{
free(hp->a);//Release the space requested by dynamic memory
hp->a = NULL; // Leave blank
hp->size = 0; //Clear
hp->capacity = 0;clear
}
//Insertion into the heap
void HeapPush(Heap* hp, HPDataType x)
{
// If there is not enough space, expand it.
if (hp->size == hp->capacity)
{
HPDataType* tmp =(HPDataType*)realloc(hp->a, sizeof(HPDataType) * hp->capacity * 2);
if (tmp == NULL)
{
perror("reallco:");
exit(-1);
}
\t\t
// Expansion may occur: in-situ expansion off-site expansion
\t\t//so
hp->a = tmp;
hp->capacity *= 2;
}
hp->a[hp->size + + ] = x;
//size -1 is the subscript of the last element
AdjustUpward(hp->a, hp->size-1);
}
//exchange function
void Swap(HPDataType* p1, HPDataType* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//Build a big pile and adjust upward
void AdjustUpward(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
//If the child's value is greater than the parent's value, swap the positions of the child and parent.
Swap( & amp;a[child], & amp;a[parent]);
// iterate --
child = parent; //update child
parent = (child - 1) / 2; //update parent
}
else
{
//Heap is completed
break;
}
}
}
//Already have a large pile as an example
void AdjustDown(HPDataType* a, int size, int parent)
{
//Assume that the left child is the older of the two children
int child = parent * 2 + 1;
//The subscript of child must be within the valid subscript of the array
while (child < size)
{
//prevent crossing the boundary
if ((child + 1 < size) & amp; & amp; a[child + 1] > a[child]) // If the right child is larger than the left child, change child to right child
{
//The elements in the array are consecutive, so the left child + 1 is the right child
+ + child; //
}
if (a[child] > a[parent])
{
Swap( & amp;a[child], & amp;a[parent]); //If the child is larger than the father, swap the positions of the child and the father.
//iterate--
parent = child; //Update parent
child = parent * 2 + 1; //Update child
}
else
{
//Heap is completed
break;
}
}
}
//In order not to destroy the heap structure
//1 First exchange the top element with the last element
//2 Delete the last element (the top element at this time)
//3 Adjust downward until a large number of conditions are met
void HeapPop(Heap* hp)
{
assert(hp);
//You need to have data in the data heap if you want to delete it
assert(hp->size > 0);
//1 First exchange the top element with the last element
Swap( & amp;hp->a[0], & amp;hp->a[hp->size - 1]);
hp->size--; //Delete the last element (the top element is deleted at this time)
//Adjust downward
AdjustDown(hp->a, hp->size, 0);
}
//Get the data at the top of the heap
HPDataType HeapTTop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
return hp->a[0];
}
//Get the number of valid data in the heap
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
//Determine whether the heap is empty
bool HeapEmpty(Heap* hp)
{
return hp->size == 0;
}
Summary
The above is all the content to be introduced in this article. If you find it helpful, you can give me three links