“This is the 17th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
💦 heap implementation
1. Heap downward adjustment algorithm
Now let's give you an array, logically viewed as a complete binary tree. We can scale it to a small heap by scaling down from the root node. The downsizing algorithm is based on the premise that the left and right subtrees must be a heap (both large and small heaps) in order to adjust.Copy the codeBuilding pile ❕ ❗
Have an array of random values, think of it as a full binary tree, and simulate heaps (heaps/small heaps)
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — the Cut — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
int array[] = {27.15.19.18.28.34.65.49.25.37}
Copy the code❓ Observe the above data ❔
The left and right subtrees below the root are small root heaps, and the heap downsizing algorithm is for this particular data structure
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — the Cut — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
❓ How should heap ❔ for this type of data
If the child is younger than the father, then switch places in pairs and continue downward until the left and right children are older than the father or move to the leaf. See the picture below for details.
❓ if the left and right subtrees are heaps, how to adjust ❔
int array[] = {27.37.28.18.19.34.65.25.49.15}
Copy the codeThe left and right subtrees of the root 37 and 28 are not satisfied: the idea here is to let the left and right subtrees be satisfied first; For the left and right subtrees 37 and 28, 37 needs to be satisfied first. And so on until the heap condition is satisfied. Just start with the first tree, the first non-leaf node
2. Create a heap
❗ here adjust ❕ from the reciprocal first non-leaf node
#include<stdio.h>
// Implement the parent-child swap function
void Swap(int* px, int* py)
{
int temp = *px;
*px = *py;
*py = temp;
}
// Implement adjustments
void AdjustDown(int* arr, int sz, int parent)
{
// Determine the left child's subscript
int child = parent * 2 + 1;
// Stop when the child's index exceeds the range of the array
while (child < sz)
{
// Identify the younger/older child
/ / left child is greater than the right child, so let the child records smaller children subscript | | (arr [child] < arr child + [1] record older child subscript)
if (arr[child] > arr[child + 1] && child + 1 < sz)
{
child++; //(if there is only one left child, it will be out of bounds, and illegal access will occur after use)
}
// Judge fathers and children
/ / the children is less than the father, the exchange, and continue to adjust the | | (arr [child] > arr parent father is greater than the big, exchange, and continue to adjust)
if (arr[child] < arr[parent])
{
Swap(&arr[child], &arr[parent]);
/ / iteration
parent = child;
// Reset the subscript of the left child (when the last leaf node is parent, make sure the child reads out of bounds, but don't care)
child = parent * 2 + 1;
}
// If the child is larger than the father, stop adjusting
else
{
break; }}}// Heap sort -> more efficient
void HeapSort(int* arr, int sz)
{
/ / build the heap
int i = 0;
// Start from the last tree, which is the parent of the last node
for (i = (sz - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, sz, i); }}int main(a)
{
// The left and right subtrees are heaps
int arr1[] = { 27.15.19.18.28.34.65.49.25.37 };
// Both the left and right subtrees are non-heap
int arr2[] = { 27.37.28.18.19.34.65.25.49.15 };
HeapSort(arr1, sizeof(arr1) / sizeof(arr1[0]));
int i = 0;
for (i = 0; i < sizeof(arr1) / sizeof(arr1[0]); i++)
{
printf("%d ", arr1[i]);
}
printf("\n");
HeapSort(arr2, sizeof(arr2) / sizeof(arr2[0]));
for (i = 0; i < sizeof(arr2) / sizeof(arr2[0]); i++)
{
printf("%d ", arr2[i]);
}
return 0;
}
Copy the code💨 Output result:
A small pile of
Lot of
3. Heap time complexity
❓ proves that the heap construction time is O(N) ❔
Since the heap is a complete binary tree, and the full binary tree is also a complete binary tree, the full binary tree is used here to prove it for simplicity (the time complexity is an approximation originally, and several more nodes will not affect the final result).Copy the code
The number of calls to build the heap is denoted by T(N) : (starting from the last non-leaf node < the penultimate layer >, in the worst case: the penultimate layer can be down-scaled at most 1 time per node; At the third layer from the bottom, each node can be down-regulated at most 2 times. At the last layer, each node can be lowered up to 3 times;)
Number of nodes at each layer ×\times× Worst case downward adjustment times:
T (N) = 2 h ^ – ^ 2 * 1 + 2 \ times h ^ – ^ 3 * 2 + \ times… . + 2 ^ ^ 0 x \ times x (h – 1)
So here we start from the top down
T (N) = 2 ^ ^ 0 x \ times x (h – 1) + ^ 1 ^ 2 * \ times * (h – 2) + 2 ^ ^ 2 * \ times * (h – 3) + 2 ^ 3 ^ * (h – 4) + \ times… . + 2^h-3^ times× 2 + 2^h-2^ times× 1
❗ dislocation subtraction ❕
Multiply both sides by 2 to get a new formula, and subtract the old formula from the new formula, as shown in the picture below
4. Heap insertion
Insert a 10 to the end of the array, then adjust the algorithm up until the heap is satisfied.
5. Delete heap
To delete the heap is to delete the data on the top of the heap, swap the data on the top of the heap with the last data, then delete the last data in the array, and then adjust the algorithm down.
6, heap code implementation
Attention ⚠ ⚠
▶ The heap is typically initialized using an array
▶ Insert data into the heap. After data is inserted, the properties of the original heap remain unchanged
Put it in the last position of the array and adjust it up
Remove the top data of the heap. After the data is deleted, the properties of the original heap remain unchanged
For efficiency, swap the first and last element, subtract, and adjust again
❗ three files are required here ❕
1️ heap. h, used for function declaration
#pragma once
/ / head
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
typedef int HPDataType;
//C++ -> priority_queue; //C++ -> priority_queue
/ / of
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
// Function declaration
/ / exchange
void Swap(int* px, int* py);
// Adjust downward
void AdjustDown(int* arr, int n, int parent);
// Adjust upward
void AdjustUp(int* a, int child);
// Initialize with an array
void HeapInit(HP* php, HPDataType* a, int n);
// Reclaim space
void HeapDestroy(HP* php);
// Insert x to keep it heap
void HeapPush(HP* php, HPDataType x);
// Delete the data at the top of the heap, leaving it as the heap
void HeapPop(HP* php);
// Get the data at the top of the heap, i.e. the maximum value
HPDataType HeapTop(HP* php);
/ / found empty
bool HeapEmpty(HP* php);
// The number of data in the heap
int HeapSize(HP* php);
/ / output
void HeapPrint(HP* php);
Copy the code2️ heap. c, used for the definition of function
#include"Heap.h"
void Swap(int* px, int* py)
{
int temp = *px;
*px = *py;
*py = temp;
}
void AdjustDown(int* arr, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (arr[child] < arr[child + 1] && child + 1 < n)
{
child++;
}
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break; }}}void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break; }}}void HeapPrint(HP* php)
{
assert(php);
int i = 0;
for (i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
// for HeapCreate, the structure is not passed in from outside, but created in its own malloc space
/* HP* HeapCreate(HPDataType* a, int n) {} */
//2. For HeapInit, define a structure outside and pass in the address of the structure
void HeapInit(HP* php, HPDataType* a, int n)
{
assert(php);
//malloc space (the same size as the current array)
php->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (php->a == NULL)
{
printf("malloc fail\n");
exit(- 1);
}
// Initialize with an array
memcpy(php->a, a, sizeof(HPDataType) * n);
php->size = n;
php->capacity = n;
/ / build the heap
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(php->a, n, i); }}void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
void HeapPush(HP* php, HPDataType x)
{
assert(php);
// Space is not enough, add capacity
if (php->size == php->capacity)
{
HPDataType* temp = (HPDataType*)realloc(php->a, php->capacity * 2 * sizeof(HPDataType));
if (temp == NULL)
{
printf("realloc fail\n");
exit(- 1);
}
else
{
php->a = temp;
}
php->capacity *= 2;
}
// Put x last
php->a[php->size] = x;
php->size++;
// Adjust upward
AdjustUp(php->a, php->size - 1);
}
void HeapPop(HP* php)
{
assert(php);
// No data was deletedassert(! HeapEmpty(php));// Swap heads and tails
Swap(&php->a[0], &php->a[php->size- 1]);
php->size--;
// Adjust downward
AdjustDown(php->a, php->size, 0);
}
HPDataType HeapTop(HP* php)
{
assert(php);
// No data is retrievedassert(! HeapEmpty(php));return php->a[0];
}
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
Copy the code3️ Test. C, used for Test function
#include"Heap.h"
void TestHeap(a)
{
int arr[] = { 27.37.28.18.19.34.65.25.49.15 };
HP hp;
HeapInit(&hp, arr, sizeof(arr)/sizeof(arr[0]));
HeapPrint(&hp);
HeapPush(&hp, 18);
HeapPrint(&hp);
HeapPush(&hp, 98);
HeapPrint(&hp);
printf("\n\n");
// Once the data structure is implemented, we can use these interfaces to implement sorting
while(! HeapEmpty(&hp)) {printf("%d ", HeapTop(&hp));
HeapPop(&hp);
}
printf("\n");
}
int main(a)
{
TestHeap();
return 0;
}
Copy the code