当前位置:网站首页>Binary tree (II) -- code implementation of heap
Binary tree (II) -- code implementation of heap
2022-07-05 22:24:00 【Thousands of people live in spring trees in the rain】
Heap uses array to realize its physical structure , utilize leftchild=2*parent+1 as well as rightchild=2*parent+2 Access parent and child nodes .
The basic structure of the heap :
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;// The dynamic array
size_t size;// Data volume
size_t capacity;// Capacity
}HP;
Initialization function of heap :
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
Heap zeroing function
void HeapDesTroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;// Don't neglect this step
php->size = php->capacity = 0;
}
When adding new elements to the heap , should :
① Keep large root pile ( Or a little pile of roots ) The original nature of is inconvenient , That is, after inserting new elements, it is still a large root heap ( Or a little pile of roots ).
② Try not to destroy the integrity of the original tree structure .
③ Adopt tail insertion , There is no need to move data in large quantities , To improve efficiency .
Functions that insert new elements into the heap (AdjustUp Adjust the function up ):
void AdjustUp(HPDataType* a,size_t child)
{
// Calculation formula of parent-child relationship ( about leftchild and rightchild All set up )
size_t parent = (child - 1) / 2;
// May continue to rise
// Here is a small pile , If you need a lot , Only adjust if Just use the symbol in
while (child>0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
// Update the relationship
child = parent;
parent = (child - 1) / 2;
// Be careful child=0 when ,parent=0, Will fall into a dead cycle .
// Don't use it size_t,parent Never less than 0
//-1/2==0
}
// We should also consider the situation of stopping in the middle
else
{
break;
}
}
}
// After inserting new data , Keep a big pile 、 The nature of small root pile
void HeapPush(HP* php, HPDataType x)
{
assert(php);
// Space is not enough , Expand first
if (php->capacity == php->size)
{
size_t newCapacity = php->capacity * 2 + 1;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc failed.\n");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
// Insert data into the heap —— Adjust the algorithm up
// First step : First put the new data in the physical structure ( The order sheet / Array ) Tail of
php->a[php->size] = x;
++php->size;
// The second step : Adjust up
AdjustUp(php->a, php->size - 1);
}
Delete the function of the root
void AdjustDown(HPDataType* a,size_t size,size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;
while (child < size)
{
// First step : Choose the younger of the left and right children
if (child + 1 < size && a[child + 1] < a[child])
{
child++;
}
// If the child is smaller than the father, exchange , And continue to adjust down
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// Delete heap top data ( Little heap - Delete the minimum data at the top of the heap / A lot - Delete the maximum data at the top of the heap )
// Keep small piles / The nature of the pile
// If you directly move the remaining data forward , There's a problem :① Destroy the structure ② The time complexity is O(N), inconvenient
// Better solution : The first data is exchanged with the last data -> Don't erase the data , direct size-- that will do -> Downward adjustments
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
// First step : The root exchanges with the last data
Swap(&php->a[0], &php->a[php->size-1]);
// The second step : Delete data
--php->size;
// The third step : Downward adjustments
// Time complexity :O(logN)
AdjustDown(php->a,php->size,0);
}
Heap sort function
// The steps of heap sorting are relatively simple , namely :
// Put all the unordered elements in the array into a new heap , In turn pop Out , That is, the ordered element column
// Heap sort —— Ascending
void HeapSort(HPDataType* a, int size)
{
// First step : Build a heap ( Little heap )
HP hp;
HeapInit(&hp);
// The second step : Put the unordered data in the array into the heap
// The third step : Because the small heap can pop up data from small to large in turn , So you can put it into the array in turn
for (int i = 0; i < size; ++i)
{
HeapPush(&hp, a[i]);
}
size_t j = 0;
while (!HeapEmpty(&hp))
{
a[j] = HeapTop(&hp);
j++;
HeapPop(&hp);
}
HeapDesTroy(&hp);
}
Complete code ( Including test cases )
Heap.h
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;// The dynamic array
size_t size;// Data volume
size_t capacity;// Capacity
}HP;
void Swap(HPDataType* pa, HPDataType* pb);
void HeapInit(HP* php);
void HeapDesTroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
void HeapPrint(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);
Heap.c
#include"Heap.h"
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
void HeapDesTroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;// Don't neglect this step
php->size = php->capacity = 0;
}
void Swap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
// The idea of algorithmic logic is binary tree , The physical operation is the data in the array
void AdjustUp(HPDataType* a,size_t child)
{
// Calculation formula of parent-child relationship ( about leftchild and rightchild All set up )
size_t parent = (child - 1) / 2;
// May continue to rise
// Here is a small pile , If you need a lot , Only adjust if Just use the symbol in
while (child>0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
// Update the relationship
child = parent;
parent = (child - 1) / 2;
// Be careful child=0 when ,parent=0, Will fall into a dead cycle .
// Don't use it size_t,parent Never less than 0
//-1/2==0
}
// We should also consider the situation of stopping in the middle
else
{
break;
}
}
}
// After inserting new data , Keep a big pile 、 The nature of small root pile
void HeapPush(HP* php, HPDataType x)
{
assert(php);
// Space is not enough , Expand first
if (php->capacity == php->size)
{
size_t newCapacity = php->capacity * 2 + 1;
HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc failed.\n");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
// Insert data into the heap —— Adjust the algorithm up
// First step : First put the new data in the physical structure ( The order sheet / Array ) Tail of
php->a[php->size] = x;
++php->size;
// The second step : Adjust up
AdjustUp(php->a, php->size - 1);
}
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; i++)
{
printf("%d ",php->a[i]);
}
printf("\n");
}
void AdjustDown(HPDataType* a,size_t size,size_t root)
{
size_t parent = root;
size_t child = parent * 2 + 1;
while (child < size)
{
// First step : Choose the younger of the left and right children
if (child + 1 < size && a[child + 1] < a[child])
{
child++;
}
// If the child is smaller than the father, exchange , And continue to adjust down
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// Delete heap top data ( Little heap - Delete the minimum data at the top of the heap / A lot - Delete the maximum data at the top of the heap )
// Keep small piles / The nature of the pile
// If you directly move the remaining data forward , There's a problem :① Destroy the structure ② The time complexity is O(N), inconvenient
// Better solution : The first data is exchanged with the last data -> Don't erase the data , direct size-- that will do -> Downward adjustments
void HeapPop(HP* php)
{
assert(php);
assert(php->size > 0);
// First step : The root exchanges with the last data
Swap(&php->a[0], &php->a[php->size-1]);
// The second step : Delete data
--php->size;
// The third step : Downward adjustments
// Time complexity :O(logN)
AdjustDown(php->a,php->size,0);
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
main.c
#include"Heap.h"
void TestHeap()
{
HP hp;
HeapInit(&hp);
HeapPush(&hp, 1);
HeapPush(&hp, 5);
HeapPush(&hp, 0);
HeapPush(&hp, 8);
HeapPush(&hp, 3);
HeapPush(&hp, 9);
HeapPrint(&hp);
HeapPop(&hp);
HeapPrint(&hp);
HeapDesTroy(&hp);
}
// The steps of heap sorting are relatively simple , namely :
// Put all the unordered elements in the array into a new heap , In turn pop Out , That is, the ordered element column
// Heap sort —— Ascending
void HeapSort(HPDataType* a, int size)
{
// First step : Build a heap ( Little heap )
HP hp;
HeapInit(&hp);
// The second step : Put the unordered data in the array into the heap
// The third step : Because the small heap can pop up data from small to large in turn , So you can put it into the array in turn
for (int i = 0; i < size; ++i)
{
HeapPush(&hp, a[i]);
}
size_t j = 0;
while (!HeapEmpty(&hp))
{
a[j] = HeapTop(&hp);
j++;
HeapPop(&hp);
}
HeapDesTroy(&hp);
}
int main()
{
TestHeap();
HPDataType a[] = { 4,2,7,8,5,1,0,6 };
HeapSort(a, sizeof(a) / sizeof(HPDataType));
for (size_t i = 0; i <= 7; i++)
printf("%d ", a[i]);
return 0;
}
边栏推荐
- Business learning of mall commodity module
- 2022 Software Test Engineer salary increase strategy, how to reach 30K in three years
- 509. Fibonacci Number. Sol
- Platform bus
- Damn, window in ie open()
- opencv 判断点在多边形内外
- Cobaltstrike builds an intranet tunnel
- Comment développer un plug - in d'applet
- Postman核心功能解析-参数化和测试报告
- Concurrency control of performance tuning methodology
猜你喜欢
Leetcode simple question: find the nearest point with the same X or Y coordinate
Granularity of blocking of concurrency control
What about data leakage? " Watson k'7 moves to eliminate security threats
Lightweight dynamic monitorable thread pool based on configuration center - dynamictp
A substring with a length of three and different characters in the leetcode simple question
Wonderful review of the digital Expo | highlight scientific research strength, and Zhongchuang computing power won the digital influence enterprise award
数博会精彩回顾 | 彰显科研实力,中创算力荣获数字化影响力企业奖
Win11 runs CMD to prompt the solution of "the requested operation needs to be promoted"
Oracle advanced query
How can Bluetooth in notebook computer be used to connect headphones
随机推荐
微服務鏈路風險分析
Database recovery strategy
Solutions for unexplained downtime of MySQL services
如何创建线程
thinkphp5.1跨域问题解决
The new content of the text component can be added through the tag_ Config set foreground and background colors
Matlab draws a cute fat doll
119. Pascal‘s Triangle II. Sol
Leetcode simple question check whether all characters appear the same number of times
2022软件测试工程师涨薪攻略,3年如何达到30K
Summary of concurrency control
Oracle views the data size of a table
Leetcode simple question: the minimum cost of buying candy at a discount
Interprocess communication in the "Chris Richardson microservice series" microservice architecture
Learning of mall permission module
QT creator 7 beta release
Three "factions" in the metauniverse
Decorator learning 01
50. Pow(x, n). O(logN) Sol
Alternating merging strings of leetcode simple questions