数据结构入门——07堆
1.堆
堆（Heap）是一种特殊的完全二叉树数据结构，具有以下两个主要特性：
- 结构特性：
- 堆是一棵完全二叉树，即除了最后一层的叶子节点外，每一层都是满的，最后一层的叶子节点从左向右依次排列。
- 堆序性：
- 大堆（Max-Heap）：对于每个节点，父节点的值大于或等于其子节点的值。大堆中，根节点的值是所有节点中最大的。
- 小堆（Min-Heap）：对于每个节点，父节点的值小于或等于其子节点的值。小堆中，根节点的值是所有节点中最小的。
2.堆的实现
2.1堆的定义
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;size_t size;size_t capacity;
}HP;2.2堆初始化
void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}2.3堆的销毁
void HeapDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}2.3打印
void HeapPrint(HP* php)
{assert(php);for (size_t i = 0; i < php->size; ++i){printf("%d ", php->a[i]);}printf("\n");
}2.4向上调整堆的顺序（小堆）
向上调整，只是传入子节点下标，类似与向下调整算法。
void Swap(HPDataType* pa, HPDataType* pb)
{HPDataType tmp = *pa;*pa = *pb;*pb = tmp;
}void AdjustUp(HPDataType* a, size_t child)
{size_t parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]) //小堆//if (a[child] > a[parent]) //大堆{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}2.5向堆中插入数据
将数据插入到最后一个，然后利用向上调整算法
void HeapPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = realloc(php->a, sizeof(HPDataType)* newCapacity);if (tmp == NULL){printf("realloc failed\n");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;++php->size;// 向上调整，控制保持是一个小堆AdjustUp(php->a, php->size - 1);
}2.6向下调整堆的顺序（小堆）
void AdjustDown(HPDataType* a, size_t size, size_t root)
{size_t parent = root;size_t child = parent * 2 + 1;while (child < size){// 1、选出左右孩子中小的那个if (child + 1 < size && a[child+1] < a[child]){++child;}// 2、如果孩子小于父亲，则交换，并继续往下调整if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}2.7删除堆顶的数据。
// 删除堆顶的数据。
void HeapPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);--php->size;AdjustDown(php->a, php->size, 0);
}
2.8判断堆是否为空
bool HeapEmpty(HP* php)
{assert(php);return php->size == 0;
}2.9查看堆的大小
size_t HeapSize(HP* php)
{assert(php);return php->size;
}2.10返回堆顶数据
HPDataType HeapTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}