Binary tree (II) -- code implementation of heap

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;
}