The implementation of [data structure] heap (C language)

tree
Tree is a kind of non-linear data structure, which is a set of n (n > = 0) finite nodes with hierarchical relationship. Ordinary binary tree is not suitable to use array to store, because there may be a lot of space waste. The complete binary tree is more suitable for sequential structure storage. In reality, we usually store the heap (a binary tree) with an array of sequential structure. It should be noted that the heap here is different from the heap in the address space of the virtual process of the operating system. One is the data structure, the other is a block of area segmentation in the memory management of the operating system.
Concept and structure of reactor
If there is a key set K = {k0, k1, k2 , kn-1}, all its elements are stored in a one-dimensional array in the order of a complete binary tree, and the following requirements are met: ki < = k2i + 1 and Ki < = k2i + 2 (KI > = k2i + 1 and Ki > = k2i + 2) I = 0, 1, 2 , it is called a small pile (or a large pile). The heap with the largest root node is called the maximum heap or the large root heap, and the heap with the smallest root node is called the minimum heap or the small root heap.
The code implementation of the heap is as follows:
heap.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <malloc.h>
#include <string.h>

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* _array;
	size_t _size;
	size_t _capacity;
}Heap;

//typdef struct Heap Heap

void HeapInit(Heap* hp, HPDataType* a, size_t n);
void HeapDestory(Heap* hp);
void HeapPrint();

void HeapPush(Heap* hp, HPDataType x);
void HeapPop(Heap* hp);
HPDataType HeapTop(Heap* hp);
size_t HeapSize(Heap* hp);
size_t HeapEmpty(Heap* hp);

void TopK();
// Heap sort
void HeapSort(int* a, int n);
void HeapTest1();

heap.c

#include "heap.h"

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustDown(HPDataType* a, size_t n, int root)
{

	size_t parent = root;
	size_t child = parent * 2 + 1;

	while (child < n)
	{
		//Look for the baby
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);

			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapInit(Heap* hp, HPDataType* a, size_t n)
{
	assert(hp && a);
	hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*n);
	hp->_size = hp->_capacity = n;
	memcpy(hp->_array, a, sizeof(HPDataType)*n);//Copy a's data

	//Build heap
	for (int i = (hp->_size - 2) / 2; i >= 0; --i)
	{
		AdjustDown(hp->_array, hp->_size, i);
	}
}

void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_array);
	hp->_array = NULL;
	hp->_size = hp->_capacity = 0;
}

void HeapPrint(Heap* hp)
{
	for (size_t i = 0; i < hp->_size; ++i)
	{
		printf("%d ", hp->_array[i]);
	}
	printf("\n");
}

void AdjustUp(HPDataType* a,size_t n, size_t child)
{
	assert(a);
	size_t 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 HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->_size == hp->_capacity)
	{
		hp->_capacity *= 2;
		hp->_array = (HPDataType*)realloc(hp->_array, hp->_capacity*sizeof(HPDataType));
		assert(hp->_array);
	}
	hp->_array[hp->_size] = x;
	hp->_size++;
	//Pile up
	AdjustUp(hp->_array, hp->_size, hp->_size - 1);
}

void HeapPop(Heap* hp)
{
	assert(hp);
	Swap(&hp->_array[0], &hp->_array[hp->_size - 1]);
	hp->_size--;

	AdjustDown(hp->_array, hp->_size, 0);
}

size_t HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

size_t HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0 ? 0 : 1;
}

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->_array[0];
}

void TopK()
{
	const size_t N = 10000;
	const size_t K = 100;
	size_t* a = (size_t*)malloc(sizeof(size_t)*N);
	for (size_t i = 0; i < N; ++i)
	{
		a[i] = rand()%100000;
	}

	a[2] = 100001;
	a[19] = 100002;
	a[23] = 100003;
	a[34] = 100004;
	a[78] = 100005;

	Heap hp;
	HeapInit(&hp, a, K);
	for (size_t i = K; i < N; ++i)
	{
		if (HeapTop(&hp) < a[i])
		{
			HeapPop(&hp);
			HeapPush(&hp, a[i]);
		}
	}
	HeapPrint(&hp);
}

//Ascending - > bulk 
void HeapSort(int* a, size_t n)
{
	assert(a);
	//Build a lot
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	size_t end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

void HeapTest1()
{
	int a[10] = { 11, 14, 9, 23, 34, 16, 24, 65, 52, 45 };
	Heap hp;
	HeapInit(&hp, a, sizeof(a) / sizeof(int));
	HeapPush(&hp, 70);
	HeapPop(&hp);
	HeapPrint(&hp);

	HeapSort(a, sizeof(a) / sizeof(int));
	for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
 

test.c

#include "heap.h"

int main()
{
	HeapTest1();
	//TopK();
	system("pause");
	return 0;
}

Posted on Sun, 03 Nov 2019 01:27:34 -0700 by hyzdufan