【数据结构】二叉树-堆

二叉树-堆

堆是一种特殊的二叉树，具有二叉树特性的同时，还具备其他特性。
堆一般使用顺序结构的数组来存储数据。

堆分为：

• 小根堆
• 大根堆

小根堆： 父节点的元素小于或等于左右子结点的元素。
大根堆： 父节点的元素大于或等于左右子节点的元素。

这里我们一大根堆为例。

//.h #pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> #include<time.h>  typedef int HPDataType;  typedef struct Heap { 	HPDataType* arr; 	int size; 	int capacity; }HP;  void HPInit(HP*php);//堆初始化 void HPDestory(HP*php);//堆的销毁  void HPPush(HP*php,HPDataType x);//堆插入数据 void HPPop(HP*php);//出堆 bool HPEmpty(HP*php);//判断堆是否为空 HPDataType HPTop(HP*php);//获取堆顶元素 HPDataType HPSize(HP*php);//堆中数据个数  void AdjustDown(HPDataType* arr, int parent, int n); void AdjustUp(HPDataType* arr, int child); void Swap(int* x, int* y);  

//.c #include"Heap.h"  void HPInit(HP* php)//堆初始化 { 	assert(php); 	php->arr = NULL; 	php->capacity = php->size = 0; }  void HPDestory(HP* php)//堆的销毁 { 	assert(php); 	if (php->arr) 	{ 		free(php->arr); 	}   	php->arr = NULL; 	php->capacity = php->size = 0; }  void Swap(int*x,int*y) { 	int tmp = *x; 	*x = *y; 	*y = tmp; }  void AdjustUp(HPDataType*arr,int child)  { 	assert(arr); 	int parent = (child - 1) / 2; 	while (child>0) 	{ 		if (arr[child]>arr[parent]) 		{ 			Swap(&arr[parent],&arr[child]); 			child = parent; 			parent = (child-1)/2; 		} 		else 		{ 			break; 		} 	} }   void HPPush(HP* php, HPDataType x)//堆插入数据 { 	assert(php);  	if (php->capacity==php->size) 	{ 		int newnode = php->capacity == 0 ? 4 : 2 * php->capacity; 		HPDataType* tmp = (HPDataType*)realloc(php->arr,newnode*sizeof(HPDataType)); 		assert(tmp);  		php->arr = tmp; 		php->capacity = newnode; 	}  	php->arr[php->size] = x; 	AdjustUp(php->arr,php->size); 	php->size++; }  void AdjustDown(HPDataType*arr,int parent,int n) { 	assert(arr); 	int child = parent * 2 + 1; 	while (child<n) 	{ 		if (child+1<n&&arr[child]<arr[child+1]) 		{ 			child++; 		} 		if (arr[child]>arr[parent]) 		{ 			Swap(&arr[child],&arr[parent]); 			parent = child; 			child = parent * 2 + 1; 		} 		else 		{ 			break; 		} 	} }   void HPPop(HP* php)//出堆 { 	assert(php&&php->size); 	Swap(&php->arr[0],&php->arr[php->size-1]); 	--php->size;  	AdjustDown(php->arr,0,php->size); }  bool HPEmpty(HP* php)//判断堆是否为空 { 	assert(php); 	return php->size == 0; }  HPDataType HPTop(HP* php)//获取堆顶元素 { 	assert(php); 	return php->arr[0]; }  HPDataType HPSize(HP* php)//堆中数据个数 { 	assert(php); 	return php->size; }