Article directory
- 1. The concept of heap
- 2. Nature of heap
- 3. Classification of heaps
- 1.Dagendui
- 2. Small root pile
- 4. Description
- 5. The structure of the heap
- 6. Heap upward adjustment
- 1.Illustration
- 2. Code implementation
- 3. Time complexity analysis
- 7. Downward adjustment of the heap
- 1. Idea:
- 2. Code implementation
- 3. Time complexity analysis
- 8. Delete the root
- 1. Idea:
- 2. Code implementation
- 3. Time complexity analysis
- 9. Create a heap
- 1. Idea:
- 2. Code implementation
- 10. Summary of all methods implemented
1. The concept of heap
Heapis the collective name for a special type of data structure in computer science. If there is a key set K = { , , ,…, }, store all its elements in a one-dimensional array in the order of a complete binary tree, and satisfy: <= and <= ( >= and > = ) i = 0, 1, 2…, it is calledsmall heap(or large heap). The heap with the largest root node is called the maximum heap or large root heap, and the heap with the smallest root node is called the minimum heap or small root heap. The nodes above are non-empty except for the last layer. The nodes on the last layer are arranged from left to right)
2. Properties of heap
Non-linear, complete binary tree. Suitable for array storage.
The heap is unordered, that is, the left and right sides can be interchanged.
The best value is always at position 0
Based on this feature, we can do a lot of things, such as the TopK problem (find the top K largest/smallest numbers in a pile of data).
For example, there are thousands of stores in the food ordering software. I want to select the ten Sichuan restaurants with the most positive reviews in the area. We don’t need to sort all the data. We only need to take out the top K largest/smallest data. Using heap sort is also more efficient.
3. Classification of heaps
1. Big root pile 2. Small root pile
1.Dagendui
Definition: Any parent node in the tree is greater than or equal to the child node.
2. Small root heap
Definition: Any parent node in the tree is less than or equal to the child node.
4. Description
The following methods are all based on small heap reasoning. If you want to implement a large heap, modify the [<] symbol and other methods to achieve it.
5. Heap structure
typedef int HPDataType;
typedef struct Heap
{<!-- -->
HPDataType* a;
int size;
int capacity;
}HP;
6. Upward adjustment of the heap
The prerequisite for upward adjustment is that there must be a heap before adjusting the position. If the purpose is to adjust it to a small pile, make sure it is a small pile before adjusting the position; if the purpose is to adjust it to a large pile, make sure it is a large pile before adjusting the position.
1. Illustration
2. Code implementation
//Adjust upward
void AdjustUp(HPDataType* a, int child)
{<!-- -->
//Pass in the array, child is the subscript of the child node
int parent = (child - 1) / 2;
//When swapping all the way to the root, stop
while (child>0)
{<!-- -->
if (a[parent] > a[child])
{<!-- -->
Swap( & amp;a[parent], & amp;a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
return;
}
}
3. Time complexity analysis
Time complexity: O(logN)
Worst case: adjust to root;
Best case scenario: no adjustments required,
Seven. Downward adjustment of the heap
The premise for downward adjustment is that the left and right subtrees must be small heaps or large heaps.
1. Idea:
As shown in the picture:
This case is to adjust the root node 40 and start adjusting downward. First, ensure that the left and right subtrees of the root node are small heaps (established from the figure).
1. Compare the parent’s two children and choose the smaller one.
2. Make an exchange
3.child>n ends
2. Code implementation
//Adjust downwards
void AdjustDown(HPDataType* a, int n, int parent)
{<!-- -->
int child = parent * 2 + 1;
//Always swap until the end of the number, which is the last position of the array
while (parent<n)
{<!-- -->
if (child + 1 < n & amp; & amp; a[child + 1] < a[child])
{<!-- -->
child + + ;
}
if (a[child] < a[parent])
{<!-- -->
Swap( & amp;a[child], & amp;a[parent]);
// Continue to adjust downwards
parent = child;
child = parent * 2 + 1;
}
else
{<!-- -->
return;
}
}
}
3. Time complexity analysis
Time complexity: O(logN)
Worst case: adjust to root;
Best case scenario: no adjustments required,
8. Delete root
1. Idea:
1. First exchange the root with the last node,
2. Delete the last node;
3. Make downward adjustments.
2. Code implementation
void HeapPop(HP* p)
{<!-- -->
assert(p);
assert(p->size > 0);
Swap( & amp;p->a[0], & amp;p->a[p->size - 1]);
--p->size;
AdjustDown(p->a, p->size, 0);
}
3. Time complexity analysis
Time complexity: O:N(logN)
9. Create a heap
The idea of creating a heap can be adjusted upward or downward. Here we talk about building a heap by adjusting upward.
Since my AdjustUp function is used to adjust the small heap, the small heap created here is also small.
1. Idea:
Pass in parameters
a: array, n: is the number of array elements
1. Open up n spaces for p->a;
2. Use the memcpy function to copy the array a to p->a
3. Use AdjustUp to adjust and gradually extend downward from 1-n-1;
2. Code implementation
//Create a small heap
void HeapInitArray(HP* p, int* a, int n)
{<!-- -->
//a: array, n: is the number of array elements
assert(p);
assert(a);
p->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (p->a == NULL)
{<!-- -->
perror("malloc fail");
exit(-1);
}
p->size = n;
p->capacity = n;
//Copy the incoming array a to p->a
memcpy(p->a, a, sizeof(HPDataType) * n);
//Adjust upward to a small heap
for (int i = 1; i < n; i + + )
{<!-- -->
AdjustUp(p->a, i);
}
}
10. Summary of all method implementations
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"
//initialization
void HeapInit(HP* p)
{
assert(p);
p->a = NULL;
p->size = 0;
p->capacity = 0;
}
//destroy
void HeapDestroy(HP* p)
{
assert(p);
free(p->a);
p->a = NULL;
p->size = p->capacity = 0;
}
//Insert data
void HeapPush(HP* p, HPDataType x)
{
//Insert from the last position
assert(p);
//Expansion
if (p->capacity == p->size)
{
//If the array is empty at the beginning, open up 4 spaces. If it is not empty, it will be expanded by 2 times each time.
int newcapacity = p->capacity==0 ? 4 : p->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(p->a, sizeof(HPDataType) * p->capacity);
if (tmp == NULL)
{
perror("realloc fial\
");
exit(-1);
}
p->a = tmp;
p->capacity = newcapacity;
}
p->a[p->size] = x;
p->size + + ;
AdjustUp(p->a, p->size-1);
}
//exchange
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//Adjust upward
void AdjustUp(HPDataType* a, int child)
{<!-- -->
//Pass in the array, child is the subscript of the child node
int parent = (child - 1) / 2;
//When swapping all the way to the root, stop
while (child>0)
{<!-- -->
if (a[parent] > a[child])
{<!-- -->
Swap( & amp;a[parent], & amp;a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
return;
}
}
//Adjust downward
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
//Always swap until the end of the number, which is the last position of the array
while (parent
if (child + 1 < n & amp; & amp; a[child + 1] < a[child])
{
child + + ;
}
if (a[child] > a[parent])
{
Swap( & amp;a[child], & amp;a[parent]);
// Continue to adjust downwards
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}
//print binary tree
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; i + + )
{
printf("%d ", php->a[i]);
}
printf("\
");
}
//Create a small heap
void HeapInitArray(HP* p, int* a, int n)
{<!-- -->
//a: array, n: is the number of array elements
assert(p);
assert(a);
p->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (p->a == NULL)
{<!-- -->
perror("malloc fail");
exit(-1);
}
p->size = n;
p->capacity = n;
//Copy the incoming array a to p->a
memcpy(p->a, a, sizeof(HPDataType) * n);
//Adjust upward to a small heap
for (int i = 1; i < n; i + + )
{<!-- -->
AdjustUp(p->a, i);
}
}
//delete root
void HeapPop(HP* p)
{<!-- -->
assert(p);
assert(p->size > 0);
Swap( & amp;p->a[0], & amp;p->a[p->size - 1]);
--p->size;
AdjustDown(p->a, p->size, 0);
}
//Get the root
HPDataType HeapTop(HP* p)
{
assert(p);
assert(p->size > 0);
return p->a[0];
}
//Short call
bool HeapEmpty(HP* p)
{
assert(p);
return p->size == 0;
}