Foreword
Heap (heap): It is the abbreviation of heap memory. The heap is dynamically allocated memory. The memory size is not fixed and will not be released automatically. The heap-the data structure is an unordered tree structure, and it also satisfies the key-value How to store key-value pairs.
1. The concept and structure of the heap
If there is a set of key codes 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…, then it is called a small heap (or a large heap). The heap with the largest root node is called the largest heap or large root heap, and the heap with the smallest root node is called the smallest heap or small root heap.
Heap Properties:
- 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.
2. Implementation of the heap
2.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.
int array[] = {27,15,19,18,28,34,65,49,25,37};
Code:
//Downward adjustment algorithm
void AdjustDown(int* a, int n, int parent)
{<!-- -->
int child = parent*2 + 1;
while (child < n)
{<!-- -->
if (child + 1 < n & & a[child] > a[child + 1])
{<!-- -->
child ++ ;
}
if (a[child] < a[parent])
{<!-- -->
Swap( &a[child], &a[parent]);
parent = child;
child = parent*2 + 1;
}
else
{<!-- -->
break;
}
}
}
2.2 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.
int a[] = {1,5,3,8,7,6};
Code:
typedef int HPDataType;
typedef struct Heap
{<!-- -->
HPDataType* a;
int size;
int capacity;
}HP;
Initialization:
//heap initialization
void HeapInit(HP* php)
{<!-- -->
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
2.3 Heap building time complexity
Because the heap is a complete binary tree, and the full binary tree is also a complete binary tree, here we use a full binary tree to prove it for simplicity (the time complexity is originally an approximation, and a few more nodes will not affect the final result):
Therefore, the time complexity of building a heap is: O(N).
2.4 heap insertion
First insert a 10 to the end of the array, and then perform an upward adjustment algorithm until the heap is satisfied.
Code:
//upward adjustment algorithm
void AdjustUp(HPDataType* a, int child)
{<!-- -->
int parent = (child - 1) >> 1;
while (child > 0)
{<!-- -->
if (a[child] < a[parent])
{<!-- -->
Swap( &a[child], &a[parent]);
child = parent;
parent = (child - 1) >> 1;
}
else
{<!-- -->
break;
}
}
}
//insert
void HeapPush(HP* php, HPDataType x)
{<!-- -->
assert(php);
if (php->capacity == php->size)
{<!-- -->
int newCapacity = (php->capacity == 0) ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{<!-- -->
printf("realloc fail\
");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
\t
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
2.5 Heap deletion
Deleting the heap is to delete the data at the top of the heap, replace the data at the top of the heap with the last data, then delete the last data in the array, and then perform the downward adjustment algorithm.
Code:
//Downward adjustment algorithm
void AdjustDown(int* a, int n, int parent)
{<!-- -->
int child = parent*2 + 1;
while (child < n)
{<!-- -->
if (child + 1 < n & & a[child] > a[child + 1])
{<!-- -->
child ++ ;
}
if (a[child] < a[parent])
{<!-- -->
Swap( &a[child], &a[parent]);
parent = child;
child = parent*2 + 1;
}
else
{<!-- -->
break;
}
}
}
// delete heap top data
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap( &php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
3. Complete code implementation of the heap
Heap.h
#pragma once #include#include #include #include #include typedef int HPDataType; typedef struct Heap {<!-- --> HPDataType* a; int size; int capacity; }HP; void Swap(HPDataType* p1, HPDataType* p2); void AdjustUp(HPDataType* a, int child); void AdjustDown(int* a, int n, int parent); 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"
// swap two elements
void Swap(HPDataType* p1, HPDataType* p2)
{
HPDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//Adjust the algorithm upwards
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) >> 1;
while (child > 0)
{
if (a[child] < a[parent])
{
Swap( &a[child], &a[parent]);
child = parent;
parent = (child - 1) >> 1;
}
else
{
break;
}
}
}
//Adjust the algorithm down
void AdjustDown(int* a, int n, int parent)
{
int child = parent*2 + 1;
while (child < n)
{
if (child + 1 < n & & a[child] > a[child + 1])
{
child ++ ;
}
if (a[child] < a[parent])
{
Swap( &a[child], &a[parent]);
parent = child;
child = parent*2 + 1;
}
else
{
break;
}
}
}
//heap initialization
void HeapInit(HP* php)
{<!-- -->
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
//destroy
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
free(php);
}
//insert
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->capacity == php->size)
{
int newCapacity = (php->capacity == 0) ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->a,sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail\
");
return;
}
php->a = tmp;
php->capacity = newCapacity;
}
\t
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
// delete heap top data
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap( &php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
//Get the top element of the heap
HPDataType HeapTop(HP*php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];
}
//judgment empty
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//Get the size of the heap
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
Test.c
#include "Heap.h"
void Test()
{<!-- -->
HP hp;
HeapInit( &hp);
int a[] = {<!-- --> 65,100,70,32,50,60 };
for (int i = 0; i < sizeof(a) / sizeof(int); i ++ )
{<!-- -->
HeapPush( &hp, a[i]);
}
while (!HeapEmpty( &hp))
{<!-- -->
int top = HeapTop( &hp);
printf("%d\
", top);
HeapPop( &hp);
}
}
void HeapSort(int* a, int n)
{<!-- -->
//Ascending order, build a large pile
//Descending order, build a small heap
//Adjust the heap downward
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{<!-- -->
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{<!-- -->
Swap( &a[0], &a[end]);
//In adjustment, select the second smallest number
AdjustDown(a, end, 0);
end--;
}
}
void CreateData()
{<!-- -->
// create data
int n = 1000;
srand((unsigned int)time(NULL));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{<!-- -->
printf("fopen fail");
return;
}
for (size_t i = 0; i < n; i ++ )
{<!-- -->
int x = rand() % 1000000;
fprintf(fin, "%d\
", x);
}
fclose(fin);
}
PrintTop(int k)
{<!-- -->
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{<!-- -->
printf("fopen fail");
return;
}
int* hipple = (int*)malloc(sizeof(int) * k);
if (hipple == NULL)
{<!-- -->
printf("malloc fail");
return;
}
for (size_t i = 0; i < k; i ++ )
{<!-- -->
fscanf(fout, "%d", &hipple[i]);
}
//Build a small heap
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{<!-- -->
AdjustDown(hipple, k, i);
}
int val = 0;
while (!feof(fout))
{<!-- -->
fscanf(fout, "%d", &val);
if (hipple[0] < val)
{<!-- -->
hipple[0] = val;
AdjustDown(hipple, k, 0);
}
}
for (size_t i = 0; i < k; i ++ )
{<!-- -->
printf("%d ", hipple[i]);
}
printf("\
");
}
int main()
{<!-- -->
//Test();
/*int a[] = { 1,4,5,7,8,3,5,9,2 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i ++ )
{
printf("%d ", a[i]);
}*/
//CreatData();
PrintTop(5);
return 0;
}
Summary
Through the realization of the heap, the understanding of the structure of the heap has been deepened, and the practical application of the heap has been understood at the same time - 1. Heap sorting and 2. TOP-K problem